MCQ - Complexity Algorithms in Data Structure
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