Question

Order the following list of functions by the big-Oh notation. Group together those functions that are big θ of one another.6nlogn 2^100 loglogn log^2n 2log^n2^2^n (√n) n^0.01 1/n 4n^3/23n^0.5 5n 2nlog^2n 2^n nlog4n4^n n^3 n^2logn 4^logn √logn

Answer 1

Answer:

The increasing order of growth

1. 1/n

2. 2^100

3. Log log n

4. Sqrt(log n)

5. Log^2 n

6. n^0.01

7. ceil(sqrt(n)), 3n^0.5

8. 2^log n , 5n

9. n log4n, 6 n log n

10. floor (2 n log^2 n)

11. 4 n^3/2

12. 4^log n

13. n^2 log n

14. n^3

15. 2^n

16. 4^n

17. 2˄2n

Explanation:

When in doubt about two functions f(n) and g(n), consider log f(n) and log g(n).

Also note that Exponential growth is faster than polynomial.

i.e. the higher the degree of polynomial, the faster the growth.

I hope this helps, cheers.