Comparing growth rate of exponential function?

Question

Suppose we have two functions f(n) = 2²ⁿ⁺¹ and g(n)=2²ⁿ. I want to compare their growth rates of these two functions using two different methods.

Method One: Take the Ratio

Let's define t(n) = f(n) / g(n). Then

t(n) = f(n) / g(n)

= 2²ⁿ⁺¹ / 2²ⁿ

= 2^{2n + 1 - 2n}

= 2²ⁿ

So we'll assume that f(n) grows much faster than g(n).

Method Two: Use Logarithms

As before, let t(n) = f(n) / g(n). Now, let's take log base two of both sides:

lg t(n) = lg (f(n) / g(n))

= lg (2²ⁿ⁺¹ / 2²ⁿ)

= lg 2²ⁿ⁺¹ - lg 2²ⁿ)

= 2ⁿ⁺¹ - 2ⁿ

Now, let's take the log base two of both sides:

lg lg t(n) = (n + 1) lg 2 / n lg 2

= (n + 1) / n

Ignoring constant term, we get lg lg t(n) = 1, which is a constant, so f(n) and g(n) should have the same growth rate.

Why am I getting the wrong answer using Method Two ?

Answer 1

I think your error is assuming the following:

If log log f(x) / log log g(x) is a constant, then f(x) = Θ(g(x)).

Here's an easy counterexample to this. Let f(x) = x² and g(x) = x. Then

log log f(x) = log log x² = log (2 log x) = log 2 + log log x

and

log log g(x) = log log x

Here, log log f(x) and log log g(x) differ just by a constant (namely, log 2), but clearly it's not true that f(x) and g(x) grow at the same rates. In other words, it's not safe to ignore constants after taking the logs of the growth rates of two functions.

There's a second error in your logic. If you compute f(n) / g(n), you get

2^{2n + 1} / 2²ⁿ

= 2^{2n+1 - 2n}

= 2²ⁿ

If you take the log of this twice, you get

lg lg 2²ⁿ

= lg 2ⁿ

= n

So it's not even true that the log log of the ratio is (n + 1) / n; instead, it's n, which still tends onward toward infinity. This would also tell you that f(n) grows much more rapidly than g(n).

Hope this helps!

Answer 2

Where you went wrong: "ignoring the constant term".

t(n) = (n+1)/n = n/n + 1/n = 1 + 1/n > 1