CCP Sorting, Searching & Big-O 3 — Questions and Answers
Question 1: What is the worst-case time complexity of searching an unsorted array of n elements?
- O(log n)
- O(1)
- O(n) (Correct answer)
- O(n²)
Correct answer: O(n)
Linear search must examine every element in the worst case when the target is absent or at the last position.
Question 2: Which sorting algorithm is most efficient when the input data is nearly sorted?
- Merge Sort
- Heap Sort
- Insertion Sort (Correct answer)
- Selection Sort
Correct answer: Insertion Sort
Insertion Sort performs O(n) comparisons on nearly sorted data because each element moves only a short distance.
Question 3: The Master Theorem is used to analyze the time complexity of:
- Iterative algorithms
- Divide-and-conquer recurrences (Correct answer)
- Graph traversals
- Hash table operations
Correct 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.
Question 4: Which of the following describes a stable sorting algorithm?
- It always runs in O(n log n)
- Equal elements maintain their original relative order (Correct answer)
- It uses no extra memory
- It works only on integers
Correct 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.
Question 5: What is the time complexity of building a max-heap from an unsorted array of n elements?
- O(n log n)
- O(n²)
- O(n) (Correct answer)
- O(log n)
Correct 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).
Question 6: If an algorithm has O(n!) complexity, it belongs to which category?
- Polynomial
- Logarithmic
- Exponential
- Super-exponential / factorial (Correct answer)
Correct 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.
Question 7: Counting Sort achieves better than O(n log n) performance under what condition?
- When the array is already sorted
- When the range of key values k is O(n) (Correct answer)
- When n is a power of 2
- When duplicate values are absent
Correct 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.
CCP Sorting, Searching & Big-O 3
What is the worst-case time complexity of searching an unsorted array of n elements?