patternMinor
is little-o notation correct after being powered by a number?
Viewed 0 times
afternumberpoweredbeingnotationcorrectlittle
Problem
I just wanted an example in which the equation given below is not correct.
$f(n) = o(g(n)) \Leftrightarrow 2^{f(n)} = o(2^{g(n)})$
$f(n) = o(g(n)) \Leftrightarrow 2^{f(n)} = o(2^{g(n)})$
Solution
Trivially: $f(n) = 0, g(n) = 1$. Then $lim_{n \to \infty} f(n)/g(n) = lim_{n \to \infty} 0 / 1 = 0$ and $lim_{n \to \infty} 2^{f(n)}/2^{g(n)} = lim_{n \to \infty} 1 / 2 \neq 0$. You may want to think if less trivial cases exist.
Context
StackExchange Computer Science Q#54291, answer score: 3
Revisions (0)
No revisions yet.