# Math Help - little oh notation and theta

1. ## 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"]

2. 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"]
$
f(n) = o(g(n))$
means $\lim_{n \to \infty} |f(n)/g(n)| = 0
$

$
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