Skip to interview prep
Apexed

66. How do you compare two growth rates such as n^(log n) versus 2^n, or (log n)^100 versus n^0.01?

MediumAlgorithm analysis

Technical
Show model answer

Take logarithms of both functions or look at the limit of their ratio. log(n^(log n)) = (log n)², while log(2^n) = n. Since (log n)² grows slower than n, n^(log n) grows slower than 2^n, although it is super-polynomial.

For (log n)^100 versus n^0.01, compare logs: 100 log log n versus 0.01 log n. Any positive power of log n eventually beats any constant multiple of log log n, so n^0.01 wins asymptotically, even though the crossover happens at astronomically large n. That is why asymptotics should be paired with a sanity check on realistic input sizes.

How do you compare two growth rates such as n^(log n) versus 2^n, or (log n)^100 versus n^0.01 — Data structures & algorithms interview question — Apexed