I'm trying to prove that c2n = o((loglog n)n) (That's little-o) for any constant c. I understand that we can prove one function grows at a smaller rate than the other by taking the limit as n approaches infinity, and I can very easily pick some arbitrary integer value for c and show that indeed ((loglog n)n) grows at a faster rate. But how do I prove this to be true for any constant c?
You want to prove that for any choice of c, the value of
limn → ∞ (c2n / (log log n)n) = 0
Notice that for any choice of c that
limn → ∞ (c2n / (log log n)n)
= limn → ∞ (c2 / log log n)n
This limit is 0 because once log log n > c2, you're raising a value less than one to the power of n, which will quickly drop to zero.
Hope this helps!