6. Give as good a big-O estimate as possible for each of these functions.a) (n2 + 8)(n + 1) b) (n log n + n2)(n3 + 2) c) (n! + 2n)(n3 + log(n2 + 1))
Question
- Give as good a big-O estimate as possible for each of these functions.a) (n2 + 8)(n + 1) b) (n log n + n2)(n3 + 2) c) (n! + 2n)(n3 + log(n2 + 1))
Solution
a) (n^2 + 8)(n + 1)
The highest degree term in this function is n^3 (from n^2 * n), so the big-O estimate is O(n^3).
b) (n log n + n^2)(n^3 + 2)
The highest degree term in this function is n^5 (from n^2 * n^3), so the big-O estimate is O(n^5).
c) (n! + 2n)(n^3 + log(n^2 + 1))
The highest degree term in this function is n! * n^3, but n! grows faster than any polynomial, so the big-O estimate is O(n! * n^3). However, we usually simplify this to O(n!).
Similar Questions
5. Arrange the functionsn , 1000 log n, n log n, 2n!, 2n, 3n, and n2/1,000,000 in a list sothat each function is big-O of the next function.
2. Determine whether each of these functions is O(x2).a) f (x) = 17x + 11 b) f (x) = x2 + 1000 c) f (x) = x log xd) 42xf x e) 2xf x f) ) f (x) = (x3 + 2x)/(2x + 1)
1. Determine whether each of these functions is O(x).a) f (x) = 10 b) f (x) = 3x + 7 c) f (x) = x2 + x + 1 d) f (x) = 5 log x
Consider the following functions.f1(n) = (log n)2023f2(n) = n2logn(nn)f3(n) = n3+ 7n2f4(n) = 2. 023nf5(n) = n log nf6(n) = n *3n2Now do the followings:a. Write a correct asymptotic upper bound for each of the above.b. Sort the functions in ascending order of their growth rate, assuming n is significantlylarge. Just write the sorted order, no need to show any simulation.
Which of the given options provides the increasing order of complexity of functions f1, f2, f3 and f4:f1(n) = 2^nf2(n) = n^(3/2)f3(n) = nLognf4(n) = n^(Logn)
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.