Explore BrainMass

Give big-O estimate for each of these function

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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)

© BrainMass Inc. brainmass.com March 22, 2019, 12:28 am ad1c9bdddf

Solution Preview

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 ...

Solution Summary

The expert gives a big-O estimate for each of these functions.