Search code examples
algorithmmathbig-ocalculus

Big-O notation confusion

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?

Solution

  • 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.