little oh notation and theta

Quote:

Originally Posted by inneedofhelp

For each pair <f, g> of functions below, list which of the following are true: f(n) = o(g(n)), f(n) = Theta(g(n)), or g(n) = o(f(n)).
a. f(n) = ln(n), g(n) = lg(n). ["ln" is log-base-e, and "lg" is log-base-2]
b. f(n) = n^2, g(n) = n*lg(n).
c. f(n) = 2^n, g(n) = 2^(2n). ["^" is "to the power"]

$<br /> f(n) = o(g(n))$ means $\lim_{n \to \infty} |f(n)/g(n)| = 0<br />$

$<br /> f(n) = \Theta(g(n))$ means $\exists M_1, M_2, n_0$ such that $M_1|g(n)|\le |f(n)| \le M_2|g(n)| \ \ \forall n>n_0$

Now try one yourself

RonL