1

If the following function is given: $f(n)=n^2+ n \ln(n)+1$. How do you prove the $\Theta$ notation?

I assume that is must be $\Theta$($n^2$). But I'm not sure how to solve it.

ajotatxe
  • 65,084
Jody
  • 39
  • 3

2 Answers2

2

It's clear that

$$n^2\le f(n),\quad \forall n\ge1$$ so $$n^2=\mathcal O(f(n))$$ moreover we have

$$\ln n\le n,\quad \forall n\ge1$$ so $$f(n)\le 3n^2 ,\quad \forall n\ge1$$ and then $$f(n)=\mathcal O(n^2)$$ so we get $$f(n)=\Theta(n^2)$$

  • Can you please explain this step(It's not clear how you get $3n^2$): $$\ln n\le n,\quad \forall n\ge1$$ so $$f(n)\le 3n^2 ,\quad \forall n\ge1$$ – Jody Oct 12 '14 at 10:24
  • Since $\ln n\le n$ so $n\ln n\le n^2$ and since $1\le n^2$ we get $$f(n)=n^2+n\ln n+1\le 3n^2$$ –  Oct 12 '14 at 10:35
1

You may write, as $n$ tends to $+\infty$, $$ \frac{f(n)}{n^2}=\frac{n^2+ n \ln n +1}{n^2}=1+\frac{\ln n}{n}+\frac{1}{n^2} $$ thus $$ \frac{f(n)}{n^2} \rightarrow 1 $$ then $f(n)=\Theta(n^2)$ moreover $f(n)\sim_{+\infty}n^2.$

Olivier Oloa
  • 120,989