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)
Question
- 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)
Solution
a) f(x) = 17x + 11 is not O(x^2) because the highest power of x in the function is 1, not 2.
b) f(x) = x^2 + 1000 is O(x^2) because the highest power of x in the function is 2.
c) f(x) = x log x is not O(x^2) because the function grows more slowly than x^2.
d) f(x) = 42x is not O(x^2) because the highest power of x in the function is 1, not 2.
e) f(x) = x^2 is O(x^2) because the highest power of x in the function is 2.
f) f(x) = (x^3 + 2x)/(2x + 1) is not O(x^2) because the highest power of x in the numerator is 3, which is greater than 2.
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
4. Determine whether x3 is O(g(x)) for each of these functions g(x).a) g(x) = x2 b) g(x) = x3 c) g(x) = x2 + x3d) g(x) = x2 + x4 e) g(x) = 3x f ) g(x) = x3/2
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))
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)
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.