FPSC- Programmer (BS-17) - PMD High Yield - 2026 — Part 2 (100 Q)

Correct Answer: A. O(n log n)
Explanation: This is the merge sort recurrence (Master theorem, case 2). ALSO KNOW (related points): • Is O(log₂ n) different from O(log₁₀ n)? → No, they are the same class, because logarithms in different bases differ only by a constant factor • What does the recurrence T(n) = T(n/2) + 1 solve to? → O(log n)

Correct Answer: B. O(n)
Explanation: The leaves dominate: there are about n leaves, each doing constant work. A tree traversal fits this recurrence. ALSO KNOW (related points): • What is the amortized cost of appending to a dynamic array that doubles its capacity when full? → O(1)

Correct Answer: A. O(n²)
Explanation: Unrolling gives n + (n - 1) + ... + 1 = n(n + 1)/2. Selection sort fits this recurrence. ALSO KNOW (related points): • What is the space complexity of a recursive factorial(n) function? → O(n), because of the call stack

Correct Answer: B. 10
Explanation: The worst case is floor(log₂ 1000) + 1 = 9 + 1 = 10 comparisons. ALSO KNOW (related points): • What does binary search require of its input? → The data must be sorted and support efficient random access • What is the best-case time complexity of linear search? → O(1) • What is the benefit of a sentinel in linear search? → It removes the index bounds check from every iteration, reducing comparisons • What is the average time complexity of interpolation search on uniformly distributed sorted data? → O(log log n) • What is the optimal block size for jump search on n elements? → √n • What is the worst-case number of comparisons for linear search on n elements when the key is absent? → n

Correct Answer: A. low + high can overflow for large indices
Explanation: This overflow bug existed for years in Java's Arrays.binarySearch. ALSO KNOW (related points): • In binary search (0-indexed, mid = (low + high) / 2) of [1, 3, 5, 7, 9, 11, 13] for 11, how many elements are compared? → 2 • In a hash table using separate chaining, what happens to lookup time as the load factor (n/m) grows large? → Average lookup time grows in proportion to the load factor (the chains get longer)

Correct Answer: D. Already sorted (or reverse-sorted) input
Explanation: Sorted input produces maximally unbalanced partitions. Randomized or median-of-three pivots avoid this. ALSO KNOW (related points): • What is the best-case complexity of bubble sort with an early-exit 'swapped' flag? → O(n)

Correct Answer: C. Insertion sort
Explanation: Merge, insertion, and bubble sort are stable. Selection, heap, and quick sort are not, in their usual implementations. ALSO KNOW (related points): • What property must the per-digit sort inside LSD radix sort have? → It must be stable • Which algorithm does Python's built-in sorted() / list.sort() use? → Timsort, a stable hybrid of merge sort and insertion sort • Which sorting algorithm is best suited to data that is too large to fit in RAM? → External merge sort • Shell sort is a generalization of which algorithm? → Insertion sort • Which statement about the C standard library function qsort() is correct? → It is not guaranteed to be stable or even to use quick sort

Correct Answer: C. O(n)
Explanation: Each element needs only one comparison. This makes insertion sort good for nearly sorted data. ALSO KNOW (related points): • What is the average-case time complexity of quick sort? → O(n log n) • Which sorting algorithm makes the fewest comparisons on input that is already sorted? → Insertion sort

Correct Answer: A. Selection sort
Explanation: Selection sort makes at most one swap per pass, even though it makes O(n²) comparisons.

Correct Answer: B. Ω(n log n)
Explanation: A decision tree with n! leaves must have a height of at least log(n!), which is Θ(n log n). ALSO KNOW (related points): • What is merge sort's worst-case time complexity? → O(n log n) • Which statement about heap sort is correct? → It runs in O(n log n) in the worst case, is in-place, and is not stable