0

I am working on a review for a test and I'm trying to figure out how to explain the following problem:

Determine if the following statement is True or False. Briefly explain why:

If $\,f(n) = (2^{n} + 2n^{2})^{1/5}$ and $\,g(n) = 4n^{5} + 8n + 2\log(n)\,$ then $\,f = O(g)$

I just graphed the two equations and saw that the statement is true, however on a test with no calculator I have no idea how to explain this efficiently.

I know that $g(n)$ can be looked at as $g'(n) = n^{5}$ for large values of $n$, but I don't really know how to rewrite $f(n)$ so that I can show a comparison to $g'(n)$.

Any help would be greatly appreciated!

$\textbf{UPDATE:}$ Our teacher posted a solution and actually said the statement was False, which doesn't make sense because $f(10) \approx 4.15$ and $g(10) \approx 400,000$ so $f$ is growing no faster than $g$ or $f = O(g)$.

Community
  • 1
steveclark
  • 229
  • $f(x) \ge \left(2^n\right)^{1/5} = \left(\sqrt[5]2\right)^n$ which is exponential. – peterwhy Dec 14 '14 at 10:21
  • 1
    $f=O(g)$ means something as $n \to \infty$. 10 is a long way from $\infty$. – Joel Dec 14 '14 at 10:21
  • 1
    Do note that $f = O(g)$ is an abuse of notation. More precise notation is $f \in O(g)$ where $O(g)$ represents the class of functions that asymptotically grow no faster than $g$. Likewise for this question the answer is expressed more precisely by $f \notin O(g)$, and in fact we have the stronger $f \in ω(g)$. – user21820 Dec 14 '14 at 11:03

1 Answers1

0

Let's look at $g$. As $n\to \infty$, the dominant thing in $g$ is $4n^5$. It's true that that's pretty big when $n=10$, and even bigger for larger $n$.

Now let's see $f$. It's perhaps a surprise, but for $f$ the dominant thing is $2^{n/5}$. This is smallish for $n=10$. It's only $4$ then. But it grows quite quickly. We don't care about $n$ as small as $10$. We want $n \to \infty$.

When $n=100$, we're looking at $4n^5 = 4*10^{10}$. And $2^{n/5}$ is about $10^6$. Let's try $n=1000$. $4n^5$ becomes $4*10^{15}$ while $2^{n/5}$ is about $10^{60}$

As a general rule if $a$ is a number greater than 1, then $a^n$ grows MUCH MUCH MUCH faster than $n^a$.

Joel
  • 485
  • Okay, so if I were to explain it I would just say something like: "As $n \to \infty$, $f(n)$ can be looked at as $2^{n/5}$ and $g(n)$ can be looked at as $n^{5}$. Since $2^{n/5}$ dominates $n^{5}$ then $f \neq O(g)$" – steveclark Dec 14 '14 at 10:30
  • That would certainly work if I were grading it. To make it a tiny bit more rigorous, it's worth making clear what the word "dominates" means in your sentence. For any constant $M$ we can find $2^{n/5}>Mn^5$ for sufficiently large $n$. So your last sentence could read: Since for any $M$, $2^{n/5}$ is bigger than $Mn^5$ for sufficiently large $n$, $f \neq O(g)$. – Joel Dec 14 '14 at 10:35
  • Awesome, thanks Joel. – steveclark Dec 14 '14 at 10:41