## 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

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

3. The complexity of linear search algorithm is

A. O(n)
B. O(log n)
C. O(n2)
D. O(n log 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)

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

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)

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

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

9. The complexity of Fibonacci series is

A. O(2n)
B. O(log n)
C. O(n2)
D. O(n log 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)