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
6. Give as good a big-O estimate as possible for each of these functions.
a) (n^2 + 8)(n + 1)
b) (n log n + n^2)(n^3 + 2)
c) (n! + 2^n)(n^3 + log(n^2 + 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
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
Which of the following time complexities indicates the slowest growing function?O(n!)O(2^n)O(n^3)O(n log n)
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.
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)
Time complexities of three algorithms are given. Which should execute the slowest for largevalues of N?(A) O(N^0.5)#(B) O(n)(C) O(logN)(D) O(log2n)(E)O(NlogN
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.