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
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
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
Explanation: The growth rate of that function will be logarithmic therefore complexity will be logarithmic.
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
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
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((3⁄2)n) then complexity will be ___________
a) constant
b) quardratic
c) exponential
d) none of the mentioned
View Answer
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
Explanation: It is O(log2n), therefore complexity will be logarithmic.
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
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
Explanation: Running time of quicksort is logarithmic whereas for bubble sort it is quadratic.
10. Time complexity of the binary search algorithm is constant.
a) True
b) False
View Answer
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.
- Practice Computer Science MCQs
- Check BCA Books
- Apply for Computer Science Internship
- Practice BCA MCQs
- Check Discrete Mathematics Books