How many single-digit multiplications does Karatsuba's algorithm perform to multiply two 2-digit numbers?
Standard multiplication requires 4 single-digit multiplications. Karatsuba reduces this to 3 single-digit multiplications using (a+b)(c+d) trick.
What is the total number of levels in the recursion tree of Merge Sort for an array of size $n = 128$?
Since 128 = $2^7$, the number of recursive levels from root (128) down to leaf nodes (1) is 7 + 1 = 8 levels.
How many inversions exist in the array [5, 4, 3, 2, 1]?
Inversion count for reverse-sorted array of size $n=5$ is n(n-1)/2 = 5*4/2 = 10.
In a binary search on a sorted array of size $n = 16, what$ is the MAXIMUM number of key comparisons needed to determine if an element is present?
log_2(16) + 1 = 4 + 1 = 5 comparisons (for range sizes 16 -> 8 -> 4 -> 2 -> 1).
If an array of size $n = 100$ is sorted using standard recursive Merge Sort, how many elements of auxiliary array memory are required for merging?
Standard Merge Sort allocates a temporary array equal to the input size $n = 100 during merging$.