Complexity Analysis MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 20, 2024

What is the time complexity of accessing an element in an array?
A) O(n)
B) O(log n)
C) O(1)
D) O(n^2)
Answer: C) O(1)

Which of the following represents the best case time complexity for bubble sort?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(1)
Answer: A) O(n)

What is the space complexity of a recursive algorithm that uses stack space?
A) O(1)
B) O(n)
C) O(n^2)
D) O(log n)
Answer: B) O(n)

Which of the following sorting algorithms has the worst case time complexity of O(n^2)?
A) Quick Sort
B) Merge Sort
C) Bubble Sort
D) Heap Sort
Answer: C) Bubble Sort

What is the time complexity of searching for an element in a balanced binary search tree?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
Answer: B) O(log n)

Which of the following algorithms has a time complexity of O(n log n) in the average case?
A) Selection Sort
B) Insertion Sort
C) Merge Sort
D) Bubble Sort
Answer: C) Merge Sort

What is the time complexity of inserting an element into a binary heap?
A) O(n)
B) O(log n)
C) O(1)
D) O(n log n)
Answer: B) O(log n)

In the context of complexity analysis, what does “big O” notation describe?
A) Worst case scenario
B) Average case scenario
C) Best case scenario
D) None of the above
Answer: A) Worst case scenario

What is the time complexity of a linear search algorithm?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Answer: C) O(n)

Which of the following is true about the time complexity of merge sort?
A) It is O(n) in all cases
B) It is O(n^2) in the worst case
C) It is O(n log n) in all cases
D) It is O(log n) in the worst case
Answer: C) It is O(n log n) in all cases

What is the average case time complexity of quicksort?
A) O(n^2)
B) O(n log n)
C) O(n)
D) O(log n)
Answer: B) O(n log n)

What is the space complexity of an iterative algorithm?
A) O(1)
B) O(n)
C) O(n^2)
D) O(log n)
Answer: A) O(1)

In which case is the time complexity of selection sort O(n^2)?
A) Best case
B) Average case
C) Worst case
D) All cases
Answer: D) All cases

What is the time complexity of an algorithm that performs n operations in each of n iterations?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(n^3)
Answer: C) O(n^2)

Which of the following represents the worst-case time complexity for a binary search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)

What is the time complexity of inserting an element at the beginning of a linked list?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Answer: A) O(1)

Which of the following is a characteristic of exponential time complexity?
A) Grows linearly
B) Grows quadratically
C) Grows rapidly with input size
D) Grows logarithmically
Answer: C) Grows rapidly with input size

What is the space complexity of depth-first search (DFS) in a graph?
A) O(1)
B) O(n)
C) O(n^2)
D) O(log n)
Answer: B) O(n)

What is the time complexity of traversing a linked list?
A) O(1)
B) O(n)
C) O(log n)
D) O(n^2)
Answer: B) O(n)

In which scenario does a linear search perform better than a binary search?
A) When the list is sorted
B) When the list is unsorted
C) When the list is very small
D) Both B and C
Answer: D) Both B and C

What is the time complexity of deleting the minimum element from a binary heap?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Answer: C) O(log n)

Which of the following is an example of a polynomial time complexity?
A) O(n^3)
B) O(2^n)
C) O(log n)
D) O(n!)
Answer: A) O(n^3)

What is the average case time complexity for inserting an element in a hash table?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
Answer: A) O(1)

Which sorting algorithm is generally not stable?
A) Merge Sort
B) Bubble Sort
C) Quick Sort
D) Insertion Sort
Answer: C) Quick Sort

What is the time complexity of counting the number of elements in a linked list?
A) O(1)
B) O(n)
C) O(log n)
D) O(n^2)
Answer: B) O(n)

Which of the following time complexities represents a linearithmic algorithm?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(n^2)
Answer: B) O(n log n)

What is the space complexity of a binary search algorithm?
A) O(1)
B) O(n)
C) O(log n)
D) O(n^2)
Answer: A) O(1)

Which algorithm has the best average-case time complexity?
A) Bubble Sort
B) Insertion Sort
C) Merge Sort
D) Quick Sort
Answer: C) Merge Sort

What is the time complexity of the worst-case scenario for binary search?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(n^2)
Answer: B) O(log n)

Which of the following statements about time complexity is true?
A) It only considers the best case
B) It can be expressed using big O notation
C) It is always linear
D) It does not consider the size of input
Answer: B) It can be expressed using big O notation

What is the average case time complexity of heap sort?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Answer: B) O(n log n)

What is the time complexity of merging two sorted arrays of size n?
A) O(1)
B) O(n)
C) O(log n)
D) O(n^2)
Answer: B) O(n)

Which of the following algorithms has the best worst-case time complexity?
A) Quick Sort
B) Merge Sort
C) Bubble Sort
D) Insertion Sort
Answer: B) Merge Sort

What is the time complexity for the Fibonacci sequence using dynamic programming?
A) O(2^n)
B) O(n)
C) O(n^2)
D) O(log n)
Answer: B) O(n)

Which of the following is a characteristic of logarithmic time complexity?
A) Reduces the size of the problem with each iteration
B) Grows linearly with input size
C) Is faster than polynomial time complexity
D) None of the above
Answer: A) Reduces the size of the problem with each iteration

What is the time complexity of a binary search tree in the worst case?
A) O(log n)
B) O(n)
C) O(n log n)
D) O(n^2)
Answer: B) O(n)

Which algorithm is considered optimal for sorting large datasets?
A) Quick Sort
B) Bubble Sort
C) Insertion Sort
D) Selection Sort
Answer: A) Quick Sort

 

Data Structures MCQs

Basic Concepts

1. Introduction to Data Structures
   • Abstract Data Types (ADT) MCQs
2. Complexity Analysis MCQs
   • Time complexity MCQs
   • Space complexity MCQs
   • Big O, Big Ω, Big Θ notations MCQs

Linear Data Structures MCQs

1. Arrays MCQs
   • One-dimensional arrays MCQs
   • Multi-dimensional arrays MCQs
   • Operations: traversal, insertion, deletion MCQs
2. Linked Lists MCQs
   • Singly linked list MCQs
   • Doubly linked list MCQs
   • Circular linked list MCQs
3. Stacks MCQs
   • Stack operations (push, pop, peek) MCQs
   • Applications of stacks (expression evaluation, recursion) MCQs
4. Queues MCQs
   • Queue operations (enqueue, dequeue, front, rear) MCQs
   • Types: Simple queue, circular queue, priority queue, deque MCQs

Non-Linear Data Structures MCQs

1. Trees MCQs
   • Binary trees MCQs
   • Binary Search Trees (BST) MCQs
   • AVL Trees MCQs
   • B-trees and B+ trees MCQs
   • Tree traversal methods (in-order, pre-order, post-order) MCQs
2. Heaps MCQs
   • Min-heap MCQs
   • Max-heap MCQs
   • Heap operations (insertion, deletion, heapify) MCQs
   • Applications of heaps (priority queues, heap sort) MCQs
3. Graphs MCQs
   • Graph representation (adjacency matrix, adjacency list) MCQs
   • Graph traversal algorithms (DFS, BFS) MCQs
   • Shortest path algorithms (Dijkstra’s, Bellman-Ford) MCQs
   • Minimum Spanning Tree (Kruskal’s, Prim’s) MCQs

Hashing MCQs MCQs

1. Hash Tables
   • Hash functions MCQs
   • Collision resolution techniques (chaining, open addressing) MCQs
   • Applications of hashing MCQs

Sorting and Searching Algorithms MCQs 

1. Sorting Algorithms MCQs
   • Bubble sort MCQs
   • Selection sort MCQs
   • Insertion sort MCQs
   • Merge sort MCQs
   • Quick sort MCQs
   • Heap sort MCQs
2. Searching Algorithms MCQs
   • Linear search MCQs
   • Binary search MCQs
   • Interpolation search MCQs

Miscellaneous

1. Memory Management in data structures MCQs
   • Dynamic memory allocation MCQs
   • Garbage collection MCQs
2. String Manipulation Algorithms MCQs
   • Pattern matching (KMP, Rabin-Karp) MCQs
   • String hashing MCQs

1. Data Structures MCQs 1
2. Data Structures MCQs 2
3. Data Structures MCQs 3
4. Data Structures MCQs 4
5. Data Structures MCQs 5
6. Stacks Solved MCQs
7. Queues MCQs
8. pointer mcqs
9. Array MCQs