M4: Divide and Conquer Flashcards
Divide and Conquer
Name two key examples of Divide-and-Conquer algorithms.
- Merge Sort
- Quick Sort
What is the general recurrence relation for Divide-and-Conquer problems?
T(n)=aT(n/b)+f(n)
In the recurrence relation T(n)=aT(n/b)+f(n), what does ‘a’ represent?
‘a’ represents the number of subproblems.
In the recurrence relation T(n)=aT(n/b)+f(n), what does ‘b’ represent?
‘b’ represents the division factor.
In the recurrence relation T(n)=aT(n/b)+f(n), what does ‘f(n)’ represent?
‘f(n)’ represents the work done outside recursion.
What is the time complexity of Merge Sort?
Θ(nlogn)
What are the steps of the Merge Sort algorithm?
- Divide array into two halves
- Recursively sort each half
- Merge the two sorted halves
What is the best-case and average time complexity of Quick Sort?
Θ(nlogn)
What is the worst-case time complexity of Quick Sort?
Θ(n^2)
List one optimization technique for Quick Sort.
- Use median-of-three for pivot selection
What is the primary limitation of Binary Search?
Requires a sorted array
What is the time complexity of Binary Search in the worst case and average case?
O(logn)
What problem does the Maximum Subarray Problem address?
Find the contiguous subarray with the maximum sum.
What is the time complexity of the brute force approach for the Maximum Subarray Problem?
O(n^2)
What is the time complexity of the Divide-and-Conquer approach for the Maximum Subarray Problem?
O(nlogn)
What is Kadane’s Algorithm used for?
Finding the maximum subarray sum in linear time.
What is the time complexity of Kadane’s Algorithm?
O(n)
In the Stock Market example, what transformation is performed to find maximum profit?
Convert stock prices into daily differences.
What is the optimal solution approach for calculating maximum profit in the Stock Market example?
One-Pass Approach
What is the time complexity of the optimal solution for the Stock Market problem?
O(n)
What is the time complexity for Merge Sort in all cases?
O(nlogn) for best, average, and worst cases.
What is the time complexity for Quick Sort in the worst case?
O(n^2)
What is the time complexity for Binary Search in the best case?
O(1)
What is the time complexity for Kadane’s Algorithm in all cases?
O(n) for best, average, and worst cases.
