Data Structure MCQ - Complexity
This section focuses on the "Complexity" of the Data Structure. These Multiple Choice Questions (mcq) should be practiced to improve the Data Structure skills required for various interviews (campus interview, walk-in interview, company interview), placement, entrance exam and other competitive examinations.
1. Which of the following case does not exist in complexity theory?
A. Best case
B. Worst case
C. Average case
D. Null case
View Answer
Ans : D
Explanation:Null case does not exist in complexity Theory.
2. What is the time, space complexity of following code:
int a = 0, b = 0;
for (i = 0; i < N; i++)
{
a = a + rand();
}
for (j = 0; j < M; j++)
{
b = b + rand();
}
A. O(N * M) time, O(1) space
B. O(N + M) time, O(N + M) space
C. O(N + M) time, O(1) space
D. O(N * M) time, O(N + M) space
View Answer
Ans : C
Explanation:The first loop is O(N) and the second loop is O(M). Since we don’t know which is bigger, we say this is O(N + M). This can also be written as O(max(N, M)).
Since there is no additional space being utilized, the space complexity is constant / O(1).
3. The complexity of linear search algorithm is
A. O(n)
B. O(log n)
C. O(n2)
D. O(n log n)
View Answer
Ans : A
Explanation: The worst case complexity of linear search is O(n).
4.What is the time complexity of following code:
int a = 0;
for (i = 0; i < N; i++)
{
for (j = N; j > i; j--)
{
a = a + i + j;
}
}
A. O(N)
B. O(N*log(N))
C. O(N * Sqrt(N))
D. O(N*N)
View Answer
Ans : D
Explanation:= N + (N – 1) + (N – 2) + … 1 + 0
= N * (N + 1) / 2
= 1/2 * N^2 + 1/2 * N
O(N^2) times.
5. The Worst case occur in linear search algorithm when
A. Item is somewhere in the middle of the array
B. Item is not in the array at all
C. Item is the last element in the array
D. Item is the last element in the array or is not there at all
View Answer
Ans : D
Explanation:The Worst case occur in linear search algorithm when Item is the last element in the array or is not there at all.
6. What is the time complexity of following code:
int i, j, k = 0;
for (i = n / 2; i <= n; i++)
{
for (j = 2; j <= n; j = j * 2)
{
k = k + n / 2;
}
}
A. O(n)
B. O(nLogn)
C. O(n^2)
D. O(n^2Logn)
View Answer
Ans : B
Explanation:Let’s take the examples here.
for n = 16, j = 2, 4, 8, 16
for n = 32, j = 2, 4, 8, 16, 32
So, j would run for O(log n) steps.
i runs for n/2 steps.
So, total steps = O(n/ 2 * log (n)) = O(n*logn)
7. The worst case occur in quick sort when
A. Pivot is the median of the array
B. Pivot is the smallest element
C. Pivot is the middle element
D. None of the mentioned
View Answer
Ans : B
Explanation:This happens when the pivot is the smallest (or the largest) element. Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements.
8. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
A. X will always be a better choice for small inputs
B. X will always be a better choice for large inputs
C. Y will always be a better choice for small inputs
D. X will always be a better choice for all inputs
View Answer
Ans : B
Explanation: An algorithm X is said to be asymptotically better than Y if X takes smaller time than y for all input sizes n larger than a value n0 where n0 > 0.
9. The complexity of Fibonacci series is
A. O(2n)
B. O(log n)
C. O(n2)
D. O(n log n)
View Answer
Ans : A
Explanation:= Fibonacci is f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1. Let g(n) = 2n. Now prove inductively that f(n) > = g(n).
10. 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).
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.
21. if for an algorithm time complexity is given by O(n2) then complexity will:
A. constant
B. quardratic
C. exponential
D. none of the mentioned
View Answer
Ans : B
Explanation: The growth rate of that function will be quadratic therefore complexity will be quardratic..
22. 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
Ans : C
Explanation: The growth rate of that function will be exponential therefore complexity will be exponential.
23. the time complexity of binary search is given by:
A. constant
B. quardratic
C. exponential
D. none of the mentioned
View Answer
Ans : D
Explanation: It is O(log2n), therefore complexity will be logarithmic.
24. The time complexity of linear search is given by:
A. O(log2n)
B. O(1)
C. exponential
D. none of the mentioned
View Answer
Ans : D
Explanation: It is O(n), therefore complexity will be linear.
25. 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
Ans : B
Explanation: Running time of quicksort is logarithmic whereas for bubble sort it is quardratic
26. State true or false
Time complexity of binary search algorithm is constant
A. True
B. False
View Answer
Ans : B
Explanation: It is O(log2n), therefore complexity will be logarithmic.
27. Two main measures for the efficiency of an algorithm are
A. Time and space
B. Processor and memory
C. Complexity and capacity
D. Data and space
View Answer
28. Which is the best data structure for round robin algorithm for CPU scheduling?
A. Stack implemented using queues
B. Doubly linked list
C. Circular queue
D. Queue implemented using stacks
View Answer
29. Which algorithm is having highest space complexity?
A. Bubble sort
B. Insertion Sort
C. Quick Sort
D. Merge Sort
View Answer
30. If the array is already sorted, then the running time for merge sort is: ?
A. O(1)
B. O(n*log n)
C. O(n)
D. O(n^2)
View Answer
Also Check :
Discussion