HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

is little-o notation correct after being powered by a number?

Submitted by: @import:stackexchange-cs··
0
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)})$

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.