# Thread: prove f(n) = Ѳ(n)

1. ## prove f(n) = Ѳ(n)

I need to prove that f(n) = Ѳ(n)

when f:N -> R defined by
$\frac{n^2+2log2n}{n+1}$

<= since log2n<=n

(I left out these works)

= 6n for n>0

since each term >= 0
>= since log2n is >= 0 for n>=1

>= $\frac{n^2}{n+n}$
= $\frac{n}{2}$ for n>0

Therefore f(n) = Ѳ(n)

is it ok?

2. For the first part, I would just go with

$\frac{n^{2}+2n}{n+1}\le\frac{n^{2}+2n+1}{n+1}=\fra c{(n+1)^{2}}{n+1}=n+1\le 2n.$

It's a sharper bound, if you care for such things.

Assuming the steps you've left out are valid, it looks ok to me.

3. Thanks Ackbeet, I'm really learning a lot of little extras from posting on this forum, things that are not covered in my lecture notes.

4. You're welcome. Have a good one!