1

given that:

$f(n) = a^n$ and $g(n) = b^n$

where, a,b are positive integers and n is a positive real number

does there exist some $f(n) \notin \mathcal{O}g(n)$?

ie. $f(n) \leq c_1 \cdot g(n)$ is false?

Gus Kenny
  • 639

2 Answers2

1

As long as $a > b$, $f(n) \not \in \mathcal{O}(g(n))$.

ml0105
  • 14,674
  • but if, say, a = 4 and b = 2, then couldnt you say that f(n) <= 0.5 g(n) and so the inequality still holds? – Gus Kenny Mar 30 '14 at 16:54
  • 1
    Consider $n = 10$. So $4^{10} = 2^{20} \geq 2^{10}$. If you wanted to switch the inequalities, $2^{10} \leq \frac{1}{2} 2^{20} = 2^{19}$. – ml0105 Mar 30 '14 at 17:02
  • ah, okay, sorry, i was getting my arithmetic all wrong. it would be the case that f(n) is in Og(n) if f(n) and g(n) were polynomial, but it is different for exponential. thanks for clearing that up, it helped me a fair bit in understanding it. – Gus Kenny Mar 30 '14 at 17:10
  • Glad I could help! – ml0105 Mar 30 '14 at 17:10
0

Let $a=4$ and $b=2$. We show that $a^n \not\in O(b^n)$. So we need to show that for every constant $c$, there are infinitely many $n$ such that $4^n \gt c(2^n)$. Equivalently, since $4^n=(2^n)(2^n)$, we want to show that there are infinitely many $n$ such that $2^n \gt c$. This is clear, since $2^n\to\infty$ as $n\to\infty$.

André Nicolas
  • 507,029
  • so then why is it not the case that an is not in O(bn)? surely this reasoning would hold if it was polynomial? a*n still tends to infinity as n tends to infinity. – Gus Kenny Mar 31 '14 at 00:22
  • Yes, but the point is that $a^n$ tends to $\infty$ much faster than $b^n$ does. – André Nicolas Mar 31 '14 at 01:09
  • For $f(n)$ to be in $O(g(n))$, the ratio $\frac{f(n)}{g(n)}$ must be $\le c$ for some constant $c$, whenever $n$ is large. The solution above shows that there is no such $c$. – André Nicolas Mar 31 '14 at 01:12