Discrete Mathematics Questions and Answers for Freshers on “Algorithms – Complexity”.
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
Answer: d
Clarification: 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
Answer: a
Clarification: 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
Answer: d
Clarification: 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
Answer: b
Clarification: 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
Answer: b
Clarification: 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
Answer: c
Clarification: 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
Answer: d
Clarification: 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
Answer: d
Clarification: 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
Answer: b
Clarification: 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
Answer: b
Clarification: It is O(log2n), therefore complexity will be logarithmic.