1
$\begingroup$

It stands to reason that $n^2+n \in \Theta(n^2)$.
But how can I formally proof it?

I tried next way:

Generalized to $f(n)+o(f(n)) \in \Theta(f(n))$ Separated to $\tag{1} f(n)+o(f(n)) \in O(f(n))$ $\tag{2} f(n)+o(f(n)) \in \Omega(f(n))$

Definitions of asymptotics says:

$o(g(n))$ = { $f(n)$: for any positive constant $c > 0$, there exists a constant $n_0 > 0$ such that $0 \leq f(n) < cg(n)$ for all $n \geq n_0$ }

$O(g(n))$ = { $f(n)$: there exists positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0$ }

$\Omega(g(n))$ = { $f(n)$: there exists positive constants $c$ and $n_0$ such that $0 \leq cg(n) \leq f(n)$ for all $n \geq n_0$ }

For $o(f(n))$ introduce $f'(n), c', n'$ so that $\tag{3} 0 \leq f'(n) < c'f(n)$, for all $n \geq n'$

For $(1)$ we must show that $0 \leq f(n) + f'(n) \leq cf(n)$ $(3) \implies f(n) + f'(n) < f(n) + c'f(n) \leq cf(n)$, for $c \geq c'+1$

For $(2)$ we must show that $0 \leq cf(n) \leq f(n) + f'(n)$ And at this point I stuck.

Where did I make mistake?
Is my reasoning correct at all?
Thanks.

Update

We can simply take $c=1$ ans as $f'(n) \geq 0 $ $ cf(n) \leq f(n) + f'(n)$

Thank you Kevin.

1 Answers 1

4

You're doing this more abstractly than is strictly necessary. All we need to show is that $n^2+n$ is bounded above by $k_1n^2$ for some $k_1$, once $n$ is big enough, and below by $k_2n^2$ for some $k_2,$ similarly. Take $k_2=1$. Then $n^2+n\geq n^2$ for all $n$. Now, what do we get from $k_1=2$?

However, as long as you're proving the more general fact you passed to: your (1) is fine. For (2), why not take $c=1$?

  • 0
    @WiseBird - If you like an answer, please be sure to accept it as well as upvote it.2012-08-02