Algorithms and Data Structures Flashcards

What is the worst-case time complexity of Merge Sort on an array of n elements?

Answer: O(n log n)

Merge Sort satisfies the recurrence T(n) = 2T(n/2) + O(n), which by the Master Theorem resolves to O(n log n) in all cases.

Which data structure is used in Breadth-First Search (BFS) to track the order in which vertices are visited?

Answer: Queue

BFS explores vertices level by level, requiring a FIFO queue so that nodes discovered earlier are processed before later-discovered nodes.

What is the worst-case time complexity of QuickSort?

Answer: O(n²)

QuickSort's worst case occurs when the pivot is always the minimum or maximum element (e.g., already-sorted input with a fixed pivot), producing unbalanced partitions and O(n²) comparisons.

In a randomly constructed Binary Search Tree (BST), what is the average-case time complexity for a search operation?

Answer: O(log n)

A randomly constructed BST has an expected height of O(log n), so search visits at most O(log n) nodes on average.

What is the height of a complete binary tree containing n nodes?

Answer: O(log n)

A complete binary tree of height h has between 2^h and 2^(h+1)−1 nodes, so h = ⌊log₂ n⌋, which is O(log n).

Which of the following sorting algorithms is both stable and guarantees O(n log n) worst-case time complexity?

Answer: Merge Sort

Merge Sort preserves the relative order of equal elements (stable) and always runs in O(n log n); HeapSort is O(n log n) but not stable, and QuickSort degrades to O(n²) worst case.

What is the time complexity of inserting an element into a max-heap containing n elements?

Answer: O(log n)

The new element is added at the last position and then sifted up through at most O(log n) levels (the height of the heap) to restore the heap property.