Divide And Conquer – GATE CSE AlgorithmsPractice Questions & PYQs

Merge sort divides into two halves and merges in linear time.

BFS is a graph traversal algorithm, not divide and conquer.

Merge Sort requires $O(n)$ auxiliary space to merge the sub-arrays. Quick Sort is $O(log n)$ for the recursion stack, and others are $O(1)$ (not D&C).

If the pivot is always the median, the array is always split into two equal halves ($n/2$). This results in the recurrence $T(n) = 2T(n/2) + Theta(n)$, which is $O(n log n)$.

Here $a=2, b=2, f(n)=n^3$. $log_b a = 1$. Since $f(n) = n^3$ is $Omega(n^{1+\epsilon})$ (Case 3), and $2(n/2)^3 le k n^3$ for $k < 1$, the complexity is $Theta(n^3)$.

Worst-case comparisons $= \lfloor \log_2 n \rfloor + 1 = \lfloor \log_2 32 \rfloor + 1 = 5 + 1 = \mathbf{6}$ comparisons. After each comparison, the search space halves: $32 \to 16 \to 8 \to 4 \to 2 \to 1 \to$ not found (6 comparisons).

Merge Sort divides the array and recursively sorts subarrays.

Here $a=8, b=2, f(n)=n^2$. $log_b a = log_2 8 = 3$. Since $f(n) = n^2$ is $O(n^{3-\epsilon})$, Case 1 of Master Theorem applies. $T(n) = Theta(n^3)$.

For optimal comparison-based sorts (like Merge Sort or Heap Sort), both the worst-case and average-case complexities are bounded by $Omega(n log n)$.

The given implementation only has a $\texttt{return mid}$ inside the loop when the key is found. If the loop exits without finding the key (when $\text{low} > \text{high}$), no return statement is executed - the function falls through. A correct implementation should have a $\texttt{return -1}$ (or similar sentinel) after the loop to indicate the key is absent. This is a common bug in binary search implementations.