Can you rank these in terms of fastest to slowest growing and explain the reasoning why
1 (constant), log2n (logarithmic), n (linear), n * log2 n (“n log n”), n2 (quadratic),
Asked
Active
Viewed 313 times
0
-
4Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – John Dec 13 '19 at 17:38
-
1Take a large n, like 10000, and substitute it in each case. – rustyx Dec 13 '19 at 18:54
1 Answers
0
If you try to decide for two function which one grows asymptotically faster, just calculate the limit of the quotient. So for two functions f(n) and g(n) calculate lim f(n)/g(n). If it is infinity f grows faster, if it is zero g grows faster and if the result is something else, they grow with the same rate.
At least for all school examples, this should work for most cases and avoids the problem of finding a "large" number. It is not always clear if a number is large in the context of a function. E.g. f(n) = log(n), g(n) = 2^-20 * n. g grows faster than f, but f(2^20) = 20 and g(2^20) = 1.
In real life one would need to use lim sup instead and sometimes it is even more complicated.
AbcAeffchen
- 14,400
- 15
- 47
- 66