Big O examples

• August 1st 2010, 04:04 PM
james12
Big O examples
Hi didn't really know where this belongs so here goes...

show that $log_eN^c=O(N) \forall c \in \mathbb{R}\setminus{0}$

and

find O(f(x)) for $f(x) = x^4 + 2^x + log_en$

Thanks a lot for the help all=)
• August 1st 2010, 08:46 PM
CaptainBlack
Quote:

Originally Posted by james12
Hi didn't really know where this belongs so here goes...

show that $\log_eN^c=O(N) \forall c \in \mathbb{R}\setminus{0}$

$\log(N^c)=c\log(N)$

Then as $\log(N) \in O(N)$, so is $c\log(N)$.

If you need to prove that: $\log(N) \in O(N)$
you use L'Hopital's rule to show that:

$\displaystyle \lim_{N \to \infty} \frac{\log(N)}{N}=0$

and the result follows from that.

CB
• August 1st 2010, 08:49 PM
CaptainBlack
Quote:

Originally Posted by james12

find O(f(x)) for $f(x) = x^4 + 2^x + log_e x$

As:

$\displaystyle \lim_{x \to \infty} \frac{x^4}{2^x}=0$

and

$\displaystyle \lim_{x \to \infty} \frac{\log_e(x)}{2^x}=0$

we can conclude:

$f(x) \in O(2^x)$

CB
• August 2nd 2010, 01:30 AM
james12
Thanks so much CaptainBlack, life saver=) =)