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
Just wondering: can I assume that 2^(loglogn)
has the same growth as 2^n
? Should I take 1.1^n
as a constant?
Big O Notation Explained with Examples Big O notation is a way to describe the speed or complexity of a given algorithm. If your current project demands a predefined algorithm, it's important to understand how fast or slow it is compared to other options. What is Big O notation and how does it work?
Changing units is equivalent to multiplying the appropriate variable by a constant wherever it appears. For example, if an algorithm runs in the order of n2, replacing n by cn means the algorithm runs in the order of c2n2, and the big O notation ignores the constant c2.
Big Omega notation. There are two very widespread and incompatible definitions of the statement where a is some real number, ∞, or −∞, where f and g are real functions defined in a neighbourhood of a, and where g is positive in this neighbourhood. The first one (chronologically) is used in analytic number theory,...
Here are some common algorithms and their run times in Big O notation: Big O notation Example algorithm O (log n) Binary search O (n) Simple search O (n * log n) Quicksort O (n2) Selection sort 1 more rows ...
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With