Big-O notation confusion

Question

I have come across some of the difficulties during doing this question. The question is: sort the following functions by order of growth from slowest to fastest:

7n^3 − 10n, 4n^2, n, n^8621909, 3n, 2^(log log n), n log n, 6n log n, n!, 1.1^n

And my answer to the question is

1. n,3n
2. nlogn, 6nlogn
3. 4n^2(which equals to n^2)
4. 7n^3 – 10n(which equals to n^3)
5. n^ 8621909
6. 2^loglogn
7. 1.1^n(exponent 2^0.1376n)
8. n!

Just wondering: can I assume that 2^(loglogn) has the same growth as 2^n? Should I take 1.1^n as a constant?

Answer 1

Just wondering can i assume that 2^(loglogn) has the same growth as 2^n?

No. Assuming that the logs are in base 2 then 2^log(n) mathematically equals to n, so 2^(log(log(n)) = log(n). And of course it does not have the same growth as 2^n.

Should I take 1.1^n as a constant?

No. 1.1^n is still an exponent by n that cannot be ignored - of course it is not a constant.

The correct order is:

2^loglogn = log(n)
n,3n
nlogn, 6nlogn
4n^2
7n^3 – 10n
n^8621909
1.1^n
n!

I suggest to take a look at the Formal definition of the Big-O notation. But, for simplicity, the top of the list goes slower to infinity than the lower functions.
If for example, you will put two of those function on a graph you will see that one function will eventually pass the other one and will go faster to infinity.

Take a look at this comparing n^2 with 2^n. You will notice that 2^n is passing n^2 and going faster to infinity.
You might also want to check the graph in this page.

Answer 2

1. 2^log(x) = x, so 2^log(log(n)) = log(n), which grows far more slower than 2ⁿ.

2. 1.1ⁿ is definitely not a constant. 1.1ⁿ tends to infinity, and a constant obviously does not.