Sorting, Searching & Big-O Flashcards

What is the worst-case time complexity of searching an unsorted array of n elements?

Answer: O(n)

Linear search must examine every element in the worst case when the target is absent or at the last position.

Which sorting algorithm is most efficient when the input data is nearly sorted?

Answer: Insertion Sort

Insertion Sort performs O(n) comparisons on nearly sorted data because each element moves only a short distance.

The Master Theorem is used to analyze the time complexity of:

Answer: Divide-and-conquer recurrences

The Master Theorem provides a formula for solving recurrences of the form T(n) = aT(n/b) + f(n) common in divide-and-conquer algorithms.

Which of the following describes a stable sorting algorithm?

Answer: Equal elements maintain their original relative order

A stable sort preserves the relative order of elements with equal keys, which matters when sorting by multiple criteria.

What is the time complexity of building a max-heap from an unsorted array of n elements?

Answer: O(n)

Using the bottom-up heapify approach, a heap can be built in O(n) time despite each heapify call being O(log n).

If an algorithm has O(n!) complexity, it belongs to which category?

Answer: Super-exponential / factorial

Factorial complexity O(n!) grows faster than exponential and is characteristic of brute-force solutions to permutation problems like the Traveling Salesman Problem.

Counting Sort achieves better than O(n log n) performance under what condition?

Answer: When the range of key values k is O(n)

Counting Sort runs in O(n + k) time; when k = O(n), this reduces to O(n), beating comparison-based lower bounds.