# Thread: Upeer and Lower bouds of big O

1. ## Upeer and Lower bouds of big O

Is my working of this problem ok?

f:N->R

f(n) = $\frac{n^2+2log2n}{n+1}
$

prove f(n) = O(n) < - - - thats big O with a "-" in it

$|f(n) | = |\frac{n^2+2log2n}{n+1}|$
= $\frac{n^2+2+log2n}{n+1}$ since each term is >=0

<= $\frac{n^2+2n}{n+1}$ since log2n<=n

<= $\frac{n^2+2n^2}{n+1}$ since n>=1

= $\frac{3n^2}{n+1}$
= $\frac{3n}{1}$
=3n

$f(n) = \frac{n^2+2log2n}{n+1}$ since each term >= 0
>= $\frac{n^2}{n+1}$ since log2n is >= 0 for n>=1
= $\frac{n}{1}$
=n

Therfore
f(n) = O(n)

I really hope i am doing this correctly
Thanks for any help and input.

2. More simple and powerful is to devide nunerator and denominator by n obtaining...

$f(n) = \frac{n^{2} + 2\ \ln 2n}{n+1} = \frac{n + 2\ \frac{\ln n}{n}}{1+\frac{1}{n}}$ (1)

... so that is...

$\lim_{n \rightarrow \infty} \frac{f(n)}{n} = 1 \rightarrow f(n) \sim n _ {n \rightarrow \infty}$ (2)

Kind regards

$\chi$ $\sigma$

3. thanks for the help Chisigma, but what is more simple to you seems a step beyond what I am learning at the moment (I think).
I just tried to answer the problem as close to the example solutions I had studied. We didn't divide the numerator, just worked it out in the style I have above.
I am VERY new to discrete maths, is my attempt at the solution completely incorrect then? or even close?

4. Hi, Can someone look at my original post, (even though I spelled "upper" incorrectly").
Chisigma gave me an answer I don't really understand. She said " a more simple and powerful...." but I don't know if this implies my attempt was ok, but could be better done, or if my attempt was wrong.
But I need to know if my attempt at the solution was way off, or good enough.

Thanks for any help/input

5. A few comments:

$\frac{3n^2}{n+1}\neq 3n$, but $\frac{3n^2}{n+1} \leq \frac{3n}{n-\frac12n}=6n$ for $n>0$

$\frac{n^2}{n+1}\neq n$, but $\frac{n^2}{n+1} \geq \frac{n^2}{n+n}=\frac n2$ for $n>0$

Also you don't need to find a lower bound, unless you're trying to show $f(n)=\Theta(n)$.

Your first argument shows $f(n)=O(n)$ and your second argument shows $f(n)=\Omega(n)$.