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


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


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


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


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


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


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


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


9. The complexity of Fibonacci series is

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

View Answer


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


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


12. The complexity of Binary search algorithm is

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

View Answer


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


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


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


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


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


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


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


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


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


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


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

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

View Answer


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


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


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

A. True
B. False

View Answer


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



* You must be logged in to add comment.