What is the time complexity recurrence relation for Merge Sort on an array of size n?
Merge sort divides the array into 2 halves (2 T(n/2)) and merges them in linear time $\Theta(n)$. By Master Theorem, T(n) = $\Theta(n log n)$.
What is the auxiliary space complexity of standard iterative or recursive Merge Sort on an array of size n?
Standard Merge Sort requires an auxiliary array of size n to merge two sorted subarrays. Thus, auxiliary space complexity is O(n).
Which recurrence relation represents the worst-case time complexity of Quick Sort?
In the worst case (e.g. sorted array with first element pivot), partition splits into 0 and n-1 elements. Recurrence is T(n) = T(n-1) + O(n) = O($n^2)$.
What is the best-case time complexity of Quick Sort on an array of size n?
In the best case, the pivot always splits the array into two equal halves of size n/2. Recurrence T(n) = 2 T(n/2) + O(n) yields $\Theta(n log n)$.
What is the time complexity recurrence relation for Strassen's matrix multiplication algorithm for two n x n matrices?
Strassen's algorithm reduces matrix multiplications from 8 to 7 for submatrices of size n/2, with $\Theta(n^2) addition$ work. By Master Theorem, T(n) = $\Theta(n^{log_2 7}) \approx O(n^2.807)$.