a) Arrange the function (1.5)^n, n^100, (log n)^3, (n^1/2)*log n, 10^n, (n!)^2, n^99 +n98 in a list so that each function is big-O of the next function.
b) Give big-O estimate for each of these functions. For the function g in your estimate f(x) is O(g(x)), use a simple function g of smallest order.
i) (n^3 + (n^2)*log n) * (log n +1) + (17 log n + 19)*(n^3 +2)
ii) (2^n +n^2)*(n^3 + 3^n)
iii) (n^n + n2^n + 5^n)*(n! +5^n)
c) Find the least integer n such that f(x) is O(x^n) for each of these functions:
i) f(x) = 2x^2 + x^3(log x)
ii) f(x) = 3x^5 + (log x )^4
iii) f(x) = (x^4 + x^2 + 1) / (x^4 +1)
iiii) f(x) = (x^3 + 5logx)/(x^4 + 1)
a) The order of arrangement is logarithms < power functions (of increasing degree) < exponential functions < factorials. so in this case, (log n)^3, sqrt(n) log n, n^99 + n^98, n^100, (1.5)^n, 10^n, (n!)^2.
b) Since the function is O(1000^x), all I have to do here is take the largest growing term from each sum and ...
The expert gives a big-O estimate for each of these functions.