Question

Arrange following rate of growth in increasing order
2N , nlogn, n2 , 1, n, log n, n!, n3

Answer 1

Explanation:

what you are interested in is the size at big numbers. And here is a rule to remember:

O(nn)>O(n!)>O(αn)>O(nα)>O(log(n))>O(1)

Where α is a constant.

If you are not sure, then you can just insert a big n and check which is the biggest (n=100):

35100=2.5⋅10154

1002=104

100⋅log2(100)=400

100⋅log(100)=200

1=1 for every n

Showing you that O(35n)>O(n2)>O(nlog2(n))>O(nlog(n))>O(1)

limn→∞f(n)g(n)=∞,

then the growth rate of f(n) is larger than the growth rate of g(n). Vice versa, if

limn→∞f(n)g(n)=0,

then the growth rate of f(n) is smaller than the growth rate of g(n).

Thus, the largest growth rate is O(35n), since

limn→∞35nnlog2nlimn→∞35n35n2+11limn→∞35n1limn→∞35nnlogn=∞,=∞,=∞,=∞.

Answer 2

Answer:

The following rate of growth in increasing order:

1,logn, n, nlogn, n², n 3, 2n, n!

Explanation:

1,logn, n, nlogn, n², n 3, 2n, n!

When the execution time of an algorithm is proportional to the logarithm of the input size, it is said to be logarithmic. To refresh your memory, let's use the well-known O(log n) time algorithm, Binary Search, to solve an interesting problem (AGGRCOW).