Arrange the following in increasing order of time complexity

Arrange them in increasing order of time complexity: n^(1/logn), nlogn, 1, n2, n3, log(log n), 2^(log n).

What will be it’s answer?

>Solution :

I’ll assume that log is log base "b".

For the first expression, we have

n ^ (1 / log n) = (b^(log n))^(1/log n) = b^(log n / log n) = b = constant.

For the last one, we have

2 ^ (log n) = 2 ^ (log_2(n) / log_2(b)) = n ^ (1/log_2(b))

So here, it depends on what b actually is:

• If b=10 (common log), then n^(1/log_2(b)) = n^0.301.
• If b=e (natural log), then n^(1/log_2(b)) = n^0.693.
• If b=2 (binary log), then n^(1/log_2(b)) = n.

So in order grouping things that are Big-Theta of each other, we have

1. Fastest: 1 and n ^ (1 / log n) (these are big-Theta of each other, they’re both onstants)
2. log log n
3. 2 ^ (log n) (the ranking doesn’t depend on b).
4. n log n
5. n^2
6. Slowest: n^3