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

1. To measure Time complexity of an algorithm Big O notation is used which:

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 complexityof 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(log_{2}n) then complexity will:

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 complexityof 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(n^{2}) then complexity will:

a) constant

b) quardratic

c) exponential

d) none of the mentioned

View Answer

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

6. If for an algorithm time complexity is given by O((^{3}⁄_{2})^{n}) then complexity will:

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(log

_{2}n), therefore complexity will be logarithmic.

8. The time complexity of linear search is given by:

a) O(log_{2}n)

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 quardratic.

10. State true or false

Time complexity of binary search algorithm is constant.

a) True

b) False

View Answer

Explanation: It is O(log

_{2}n), 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__.