This set of Discrete Mathematics Multiple Choice s & Answers (MCQs) focuses on “Growth of Functions”.

1. If f(x) = (x^{3} – 1) / (3x + 1) then f(x) is

a) O(x^{2})

b) O(x)

c) O(x^{2} / 3)

d) O(1)

View Answer

Explanation: 0 <(x

^{3}– 1) / (3x + 1) < x

^{2}.

2. If f(x) = 3x^{2} + x^{3}logx, then f(x) is

a) O(x^{2})

b) O(x^{3})

c) O(x)

d) O(1)

View Answer

Explanation: 0 < 3x

^{2}< x

^{3}, it follows that 0 < 3x

^{2}+ x

^{3}logx < x

^{3}. Consequently, f(x) = O(x

^{3}).

3. The big-O notation for f(n) = (nlogn + n^{2})(n^{3} + 2) is

a) O(n^{2})

b) O(3^{n})

c) O(n^{4})

d) O(n^{5})

View Answer

Explanation: 0 < n

^{3}+ 2 < n

^{3}, it follows that (nlogn + n

^{2})(n

^{3}+ 2) is less than equal to n

^{5}.

4. The big-theta notation for function f(n) = 2n^{3} + n – 1 is

a) n

b) n^{2}

c) n^{3}

d) n^{4}

View Answer

Explanation: 2n

^{3}+ n – 1 is less than equal to n

^{3}.

5. The big-theta notation for f(n) = nlog(n^{2} + 1) + n^{2}logn is

a) n^{2}logn

b) n^{2}

c) logn

d) nlog(n^{2})

View Answer

Explanation: n

^{2}logn < n

^{3}, it follows that nlog(n

^{2}+ 1) + n

^{2}logn is less than n

^{3}and greater than n

^{2}logn.

5. The big-omega notation for f(x, y) = x^{5}y^{3} + x^{4}y^{4} + x^{3}y^{5} is

a) x^{5}y^{3}

b) x^{5}y^{5}

c) x^{3}y^{3}

d) x^{4}y^{4}

View Answer

Explanation: x

^{5}y

^{3}, x

^{4}y

^{4}and x

^{3}y

^{5}is greater than or equal to x

^{3}y

^{3}.

6. If f_{1}(x) is O(g(x)) and f_{2}(x) is o(g(x)), then f_{1}(x) + f_{2}(x) is

a) O(g(x))

b) o(g(x))

c) O(g(x)) + o(g(x))

d) None of these

View Answer

Explanation: f

_{2}(x) is less than O(g(x)). So, f

_{1}(x) + f

_{2}(x) upper bound is O(g(x)).

7. The little-o notation for f(x) = xlogx is

a) x

b) x^{3}

c) x^{2}

d) xlogx

View Answer

Explanation: Find the limit for xlogx / x

^{2}as x tends to infinity.

8. The big-O notation for f(n) = 2log(n!) + (n^{2} + 1)logn is

a) n

b) n^{2}

c) nlogn

d) n^{2}logn

View Answer

Explanation: log(n!) < n

^{2}logn, it follows that 2log(n!) + (n

^{2}+ 1)logn is less than or equal n

^{2}logn.

9. The big-O notation for f(x) = 5logx is

a) 1

b) x

c) x^{2}

d) x^{3}

View Answer

Explanation: logx < x, it follows that 5logx < x. [/expand] 10. The big-Omega notation for f(x) = 2x

^{4}+ x

^{2}– 4 is

a) x

^{2}

b) x

^{3}

c) x

d) x

^{4}

View Answer Answer: d

Explanation: 2x

^{4}+ x

^{2}– 4 is greater than or equal to x

^{4}.

Here’s the list of Best Reference Books in Discrete Mathematics

__here is complete set of 1000+ Multiple Choice s and Answers on Discrete Mathematics__.