Let $f(n) = n^3(5+2\cos(2n))$ and $g(n) = 3n^2+4n^3+5n$. Given these two functions, I must determine the appropriate symbol where the underscore is: $f(n) \in \_(g(n))$
So, first thing to do is take the limit: $\lim_{n\to\infty}\frac{f(n)}{g(n)}=\lim_{n\to\infty}\frac{5n^3 + 2n^3\cos(2n)}{3n^2 + 4n^3 + 5n}$ As n becomes very large, $3n^2 + 5n$ in the denominator become insignificant. So we get: $\lim_{n\to\infty}\frac{5n^3 + 2n^3\cos(2n)}{4n^3}$ The $\cos$ function will oscillate between $-1$ and $1$. Things get a little sketchy here...I'm not sure if I can do this, but: \lim_{n\to\infty}\frac{5n^3 ± 2n^3}{4n^3} Which makes the limit as $n\to\infty$ in the range of $\frac{3}{4}$ to $\frac{7}{4}$ inclusive. Since the limit range is contained in $[0,\infty)$, then that means $f(n)\in \Theta(g(n))$. Or, is $f(n) \notin \Theta(g(n))$ because the limit is not set to a single value?
Determine if function is little-o, little-omega or big-theta
3
$\begingroup$
algorithms
computer-science
notation
asymptotics
1 Answers
2
Theta notation does not demand the limit will be a single value; it only demands that $C_1f(n)\le g(n)\le C_2 f(n)$ for large values of $n$. You may as well work with $\limsup$ and $\liminf$ here.
-
0Thank you very much for your response! – 2011-05-17