+1 vote

O(n)

O(n2)

O(n3)

O(log n^ log n)

O(log log n ^ log log n)

O(log n ^ log log n)

in Asymptotic Analysis by AlgoMeister (1.6k points)

2 Answers

+2 votes
 
Best answer

Here is my answer:

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

2. O(log n ^ log log n)

3. O(n)

4. O(n2)

5. O(n3)

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. n3= 8^k

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

by AlgoMeister (696 points)
selected by
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))?
+1 vote

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(n2)

6. O(n3)

by AlgoMeister (920 points)
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.
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...