Discrete Mathematics Multiple Choice s on “Growth of Functions”.
1. If f(x) = (x3 – 1) / (3x + 1) then f(x) is?
a) O(x2)
b) O(x)
c) O(x2 / 3)
d) O(1)
Answer: a
Clarification: 0 < (x3 – 1) / (3x + 1) 2.
2. If f(x) = 3x2 + x3logx, then f(x) is?
a) O(x2)
b) O(x3)
c) O(x)
d) O(1)
Answer: b
Clarification: 0 < 3x2 < x3, it follows that 0 < 3x2 + x3logx < x3. Consequently, f(x) = O(x3).
3. The big-O notation for f(n) = (nlogn + n2)(n3 + 2) is?
a) O(n2)
b) O(3n)
c) O(n4)
d) O(n5)
Answer: d
Clarification: 0 < n3 + 2 < n3, it follows that (nlogn + n2)(n3 + 2) is less than equal to n5.
4. The big-theta notation for function f(n) = 2n3 + n – 1 is?
a) n
b) n2
c) n3
d) n4
Answer: c
Clarification: 2n3 + n – 1 is less than equal to n3.
5. The big-theta notation for f(n) = nlog(n2 + 1) + n2logn is?
a) n2logn
b) n2
c) logn
d) nlog(n2)
Answer: a
Clarification: n2logn < n3, it follows that nlog(n2 + 1) + n2logn is less than n3 and greater than n2logn.
5. The big-omega notation for f(x, y) = x5y3 + x4y4 + x3y5 is?
a) x5y3
b) x5y5
c) x3y3
d) x4y4
Answer: c
Clarification: x5y3, x4y4 and x3y5 is greater than or equal to x3y3.
6. If f1(x) is O(g(x)) and f2(x) is o(g(x)), then f1(x) + f2(x) is?
a) O(g(x))
b) o(g(x))
c) O(g(x)) + o(g(x))
d) None of the mentioned
Answer: a
Clarification: f2(x) is less than O(g(x)). So, f1(x) + f2(x) upper bound is O(g(x)).
7. The little-o notation for f(x) = xlogx is?
a) x
b) x3
c) x2
d) xlogx
Answer: c
Clarification: Find the limit for xlogx / x2 as x tends to infinity.
8. The big-O notation for f(n) = 2log(n!) + (n2 + 1)logn is?
a) n
b) n2
c) nlogn
d) n2logn
Answer: d
Clarification: log(n!) < n2logn, it follows that 2log(n!) + (n2 + 1)logn is less than or equal n2logn.
9. The big-O notation for f(x) = 5logx is?
a) 1
b) x
c) x2
d) x3
Answer: b
Clarification: logx < x, it follows that 5logx < x.
10. The big-Omega notation for f(x) = 2x4 + x2 – 4 is?
a) x2
b) x3
c) x
d) x4
Answer: d
Clarification: 2x4 + x2 – 4 is greater than or equal to x4.