How many scalar multiplications are required to compute $x^16$ using Divide and Conquer fast exponentiation?
$x^2$ = x*x (1), $x^4$ = ($x^2$)^2 (2), $x^8$ = ($x^4$)^2 (3), $x^16$ = ($x^8$)^2 (4). Total = 4 multiplications.
How many scalar multiplications are required to compute $x^15$ using Divide and Conquer fast exponentiation ($x^15$ = x * ($x^7$)^2)?
$x^2$ = x*x (1), $x^3$ = x*$x^2$ (2), $x^6$ = ($x^3$)^2 (3), $x^7$ = x*$x^6$ (4), $x^14$ = ($x^7$)^2 (5), $x^15$ = x*$x^14$ (6). Total = 6 multiplications.
Two sorted arrays A of size 5 and B of size 5 are merged. What is the WORST-CASE number of comparisons required during the merge step?
Max comparisons to merge sorted arrays of size m and $n = m + n - 1$. For m = 5, n = 5: 5 + 5 - 1 = 9.
In the best-case execution of Quick Sort on an array of size $n = 7 (where every pivot splits$ the array into equal halves), what is the exact total number of comparisons made during partitioning?
Each partition of a subarray of size k uses k-1 comparisons. With balanced splits for $n=7$, the partition sizes are 7, 3, and 3 (then 1-element subarrays), so total comparisons = 6 + 2 + 2 = 10.
In the worst-case execution of Quick Sort on an array of size $n = 5 (pivot always picks$ the extreme element), how many total comparisons are made?
Comparisons at each step: (5-1) + (4-1) + (3-1) + (2-1) = 4 + 3 + 2 + 1 = 10.