## Complexity Algorithms MCQ

11. What is the time complexity of following code:

int a = 0, i = N;

while (i > 0) {

a += i;

i /= 2;

}

A. O(N)

B. O(Sqrt(N))

C. O(N / 2)

D. O(log N)

View Answer

Ans : D

Explanation: We have to find the smallest x such that N / 2^x N
x = log(N)

12. The complexity of Binary search algorithm is

A. O(n)

B. O(log )

C. O(n2)

D. O(n log n)

View Answer

Ans : B

Explanation: The compexity of binary search is O(logn).

13. The complexity of merge sort algorithm is

A. O(n)

B. O(log n)

C. O(n2)

D. O(n log n)

View Answer

Ans : D

Explanation: The worst case complexity for merge sort is O(nlogn)..

14. The complexity of Bubble sort algorithm is

A. O(n)

B. O(log n)

C. O(n2)

D. O(n log n)

View Answer

Ans : C

Explanation: The worst case complexity for Bubble sort is O(n2)ans best case is O(n)/.

15. The worst case complexity for insertion sort is

A. O(n)

B. O(log n)

C. O(n2)

D. O(n log n)

View Answer

Ans : C

Explanation: In worst case nth comparison are required to insert the nth element into correct position.

16. The worst case complexity of quick sort is

A. O(n)

B. O(log n)

C. O(n2)

D. O(n log n)

View Answer

Ans : C

Explanation: The worst case complexity of quick sort is O(n2).

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

Ans : D

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

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

Ans : A

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

19.If for an algorithm time complexity is given by O(log2n) then complexity will:

A. constant

B. polynomial

C. exponential

D. none of the mentioned

View Answer

Ans : D

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

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

Ans : B

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

**Also Check : **

Discussion