Arrange the function (1.5)^n, n^100, (log n)^3, sqrt(n)*logn, 10^n, (n!)^2, and n^99+n^98 in a list so that each function is big-O of the next function.
Stuck on this problem for my discrete math class. Any help is greatly appreciated.
Stuck on this problem for my discrete math class. Any help is greatly appreciated.
-
Idea: logarithms < power functions (of increasing degree) < exponential functions < factorials.
(log n)^3, sqrt(n) log n, n^99 + n^98, n^100, (1.5)^n, 10^n, (n!)^2
Note: sqrt(n) log n is O(n^(1/2 + d)) for any d > 0.
That's why it's ordered ahead of (log n)^3, which is O(n^d) for any d > 0, like d < 1/2.
I hope this helps!
(log n)^3, sqrt(n) log n, n^99 + n^98, n^100, (1.5)^n, 10^n, (n!)^2
Note: sqrt(n) log n is O(n^(1/2 + d)) for any d > 0.
That's why it's ordered ahead of (log n)^3, which is O(n^d) for any d > 0, like d < 1/2.
I hope this helps!