• Data Structure Reference

• Other Reference

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

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)

12. The complexity of Binary search algorithm is

A. O(n)
B. O(log )
C. O(n2)
D. O(n log n)

13. The complexity of merge sort algorithm is

A. O(n)
B. O(log n)
C. O(n2)
D. O(n log n)

14. The complexity of Bubble sort algorithm is

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

16. The worst case complexity of quick sort is

A. O(n)
B. O(log n)
C. O(n2)
D. O(n log n)

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

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

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

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

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

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

23. the time complexity of binary search is given by:

A. constant
B. quardratic
C. exponential
D. none of the mentioned

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

A. O(log2n)
B. O(1)
C. exponential
D. none of the mentioned

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

26. State true or false
Time complexity of binary search algorithm is constant

A. True
B. False

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

28. Which is the best data structure for round robin algorithm for CPU scheduling?

A. Stack implemented using queues
C. Circular queue
D. Queue implemented using stacks

29. Which algorithm is having highest space complexity?

A. Bubble sort
B. Insertion Sort
C. Quick Sort
D. Merge Sort

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)

Also Check :

Discussion