Consider a Divide and Conquer recurrence T(n) = 3 T(n/4) + n for problem size n. What is its asymptotic tight bound ($\Theta$)?
Here $a=3$, $b=4$, $n^{log_4$ 3} $\approx n^0.793$. Since f(n) = $n = \Omega(n^{0.793+\epsilon})$, by Master Theorem Case 3, T(n) = $\Theta(n)$.
What is the time complexity of Karatsuba's fast integer multiplication algorithm for multiplying two n-digit numbers?
Karatsuba reduces 4 half-size multiplications to 3 multiplications. Recurrence T(n) = 3 T(n/2) + O(n) yields O($n^{log_2$ 3}) $\approx O(n^1.585)$.
Which of the following sorting algorithms uses the Divide and Conquer strategy?
Merge Sort (divide array, merge sorted halves) and Quick Sort (partition around pivot, sort sub-arrays) are classic Divide and Conquer algorithms.
What is the maximum number of edges on a recursive call chain for standard Merge Sort on an array of size n?
Each recursive step halves the problem size. The longest root-to-base-case path has ceil(log_2 n) edges, while the number of active call frames would be ceil(log_2 n) + 1 if the base-case frame is counted.
In Quick Sort, if the pivot always splits the array in ratio 1:9 (10% and 90%), what is the asymptotic time complexity?
Recurrence T(n) = T(n/10) + T(9n/10) + O(n). By recursion tree method, tree depth is log_{10/9} n, and work at each level is O(n), yielding $\Theta(n log n)$.