little oh notation and theta

• Sep 3rd 2007, 06:51 PM
inneedofhelp
little oh notation and theta
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"]
• Sep 3rd 2007, 09:30 PM
CaptainBlack
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"]

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

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

Now try one yourself

RonL