Order these time complexities from best (lowest) to worst (highest)

Question

O(n)

O(n²)

O(n³)

O(log n^ log n)

O(log log n ^ log log n)

O(log n ^ log log n)

Answer 1

Here is my answer:

1. O(log log n ^ log log n)

2. O(log n ^ log log n)

3. O(n)

4. O(n²)

5. O(n³)

6.O(log n^ log n)

Comparing 2 and 3,

Let n=2^(2^k),

2. log n ^ log log n = (2^k)^k = 2^(k^2)

3. n = 2^(2^k)

Comparing 5 and 6,

Let n=2^k,

5. n³= 8^k

6.O(log n^ log n) = k^k

Comments

I like how easily you compare 5 and 6. :-)

---

I have a question regarding the comparison between 5&6.

Let n=2^k,
5. n^3= 8^k
6. O(log n^ log n) = k^k

Why is k^k bigger than 8^k?

---

@Amal_Q Because 8 is constant, and k grows.

---

8^k is an exponential which grows very fast comparing to k^k (polynomial). Is this right?

---

k^k is not polynomial as it's k to the power of k, not k to the power of some constant. As Professor suggested, when k>8, k^k always bigger than 8^k.

---

a question, log is base 10 not base 2, log n ^ log log n = (2^k)^k = 2^(k^2) when log is base 2, but this is wrong

---

In computer science, log n usually imply log with base 2.

---

Hi Mingyu, I wonder when you see log n^ log n, how do you know it's (log n)^(log n) instead of log(n^(log n))?

Answer 2

1. O(log log n ^ log log n)

2. O(log n ^ log log n)

3. O(log n^ log n)

4. O(n)

5. O(n²)

6. O(n³)

Comments

O(n) vs O(log n ^ log n), if n < 4, O(n) is better. How to deal with it?

---

(log n) ^ (log n) is small omega (n^3), so it should come the last.