> > hi all ,I am talking about the big-Oh notation ,
> > I had to prove that
> > [lg n] ^2 is better than the n .
>
> > how can I do that . I have tried to show that n is a big-oh of ([lg n]
> > ^2) ,but
> > how can I do that ?
I hope proving (lg n)^b = o( n^a) , a,b>0 & o here denotes small-Oh,
should suffice the needs of the problem.
i.e. proving lim ((lg n)^b)/(n^a) , n ->infinity = 0 should be
sufficient.
Proceeding with b=2, a=1.
<=>Using L' Hospitals rule, as both numerator and denominator tends to
inf. as n tends to inf. we can write
LHS = lim (2 * lg n * (1/n)) / (1) , n-> infinity
= 2 * lim (lg n)/(n) , n->inf
= 2 * lim (1/n)/(1) , n->inf , using the same L'Hospitals Rule.
= 0
= RHS, hence proved. :)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
