Discrete Mathematics Questions and Answers – Algorithms – Complexity-2

This set of Discrete Mathematics Questions and Answers for Freshers focuses on “Algorithms – Complexity-2”.

1. Which is used to measure the Time complexity of an algorithm Big O notation?
a) describes limiting behaviour of the function
b) characterises a function based on growth of function
c) upper bound on growth rate of the function
d) all of the mentioned
View Answer

Answer: d
Explanation: Big O notation describes limiting behaviour, and also gives upper bound on growth rate of a function.

2. If for an algorithm time complexity is given by O(1) then the complexity of it is ____________
a) constant
b) polynomial
c) exponential
d) none of the mentioned
View Answer

Answer: a
Explanation: The growth rate of that function will be constant.

3. If for an algorithm time complexity is given by O(log2n) then complexity will be ___________
a) constant
b) polynomial
c) exponential
d) none of the mentioned
View Answer

Answer: d
Explanation: The growth rate of that function will be logarithmic therefore complexity will be logarithmic.
advertisement
advertisement

4. If for an algorithm time complexity is given by O(n) then the complexity of it is ___________
a) constant
b) linear
c) exponential
d) none of the mentioned
View Answer

Answer: b
Explanation: The growth rate of that function will be linear.

5. If for an algorithm time complexity is given by O(n2) then complexity will ___________
a) constant
b) quadratic
c) exponential
d) none of the mentioned
View Answer

Answer: b
Explanation: The growth rate of that function will be quadratic therefore complexity will be quadratic.

6. If for an algorithm time complexity is given by O((32)n) then complexity will be ___________
a) constant
b) quardratic
c) exponential
d) none of the mentioned
View Answer

Answer: c
Explanation: The growth rate of that function will be exponential therefore complexity will be exponential.

7. The time complexity of binary search is given by ___________
a) constant
b) quardratic
c) exponential
d) none of the mentioned
View Answer

Answer: d
Explanation: It is O(log2n), therefore complexity will be logarithmic.
advertisement

8. The time complexity of the linear search is given by ___________
a) O(log2n)
b) O(1)
c) exponential
d) none of the mentioned
View Answer

Answer: d
Explanation: It is O(n), therefore complexity will be linear.

9. Which algorithm is better for sorting between bubble sort and quicksort?
a) bubble sort
b) quick sort
c) both are equally good
d) none of the mentioned
View Answer

Answer: b
Explanation: Running time of quicksort is logarithmic whereas for bubble sort it is quadratic.
advertisement

10. Time complexity of the binary search algorithm is constant.
a) True
b) False
View Answer

Answer: b
Explanation: It is O(log2n), therefore complexity will be logarithmic.

Sanfoundry Global Education & Learning Series – Discrete Mathematics.

To practice all areas of Discrete Mathematics for Freshers, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.