1
$\begingroup$

i have $f(n)=n^3+n\log^2n$ and i was trieng to prove that $f(n)=n^3+n\log^2n$ = $\theta(n^3)$. but i feel that i am doing it all wrong , which means i understand why the statent is true but i don't know if the way i proved it was enough.. here is what i did so far :

first i need to prove that : $f(n)=n^3+n\log^2n$ = $O(n^3)$ We can choose constant C like this : if we devide the equation with $n^3$ then we get : $1+n\log^2n/n^3$ $<=$ $C $ but $n\log^2n/n^3$ <= 1 for every n so if we choose C to be C>=2 then this will be proved.

second i need to prove :$f(n)=n^3+n\log^2n$ = $pi(n^3)$ this i think doesn't need to be proved because if i choose any C<1 then for every n we will get : $n^3+n\log^2n$ >= $C(n^3)$

here is

$\endgroup$
1
  • $\begingroup$ What are $\theta$ and pi?..... BTW the codes \le and \leq give $\le$ while \ge and \geq give $\ge$. $\endgroup$ Nov 21, 2018 at 7:03

1 Answer 1

1
$\begingroup$

Hint: $\lim_{n \to \infty} \frac{\log n}{\sqrt n} = (\infty / \infty) = (by L'Hospital) \lim_{n \to \infty}\frac{2\sqrt n}{n} =0$

$\endgroup$
3
  • $\begingroup$ i didn't really understand the hint .. is this a way toprove that nlog2n/n3 <= 1 ? $\endgroup$
    – jasmin
    Nov 20, 2018 at 20:12
  • $\begingroup$ @jasmin: basically, $\log n$ grows slower than $\sqrt n$ so $\log^2 n$ grows slower than $n$ which means $n\log^2 n/n^3< 1/n \le 1$ $\endgroup$
    – Vasili
    Nov 20, 2018 at 20:35
  • 1
    $\begingroup$ To the proposer: For any positive $A,B$ we have $ \lim_{x\to \infty}(\ln x)^A/x^B=0.$ $\endgroup$ Nov 21, 2018 at 7:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .