Big-O Note Recognition

Question

I ran into some difficulties in doing this. The question arises: sort the following functions in order of growth from the slowest to the 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

• n, 3n
• nlogn, 6nlogn
• 4n ^ 2 (which equals n ^ 2)
• 7n ^ 3 - 10n (which equals n ^ 3)
• n ^ 8621909
• 2 ^ loglogn
• 1.1 ^ n (exponent 2 ^ 0.1376n)
• P!

Just curious: can I assume that 2^(loglogn) has the same height 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 height as 2 ^ n?

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

Should I use 1.1 ^ n as a constant?

No. 1.1^n is still an exponent of 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 taking a look at the Big-O Formal Definition of Notation . But for simplicity, the top of the list goes slower to infinity than the bottom functions.
If, for example, you place two of these functions on a graph, you will see that one of the functions will eventually transfer the other and will go faster to infinity.

See this by comparing n^2 with 2^n . You will notice that 2^n goes through n^2 and goes faster to infinity.
You can also check the schedule on this page .

Answer 2

• 2 ^{log (x)} = x, therefore 2 ^{log (log (n))} = log (n), which grows much more slowly than 2 ^p .

• 1.1 ^{n is} definitely not a constant. 1.1 ⁿ tends to infinity, and the constant, obviously, does not.