The most well-known algorithm design technique.
TODO
If a recurrence relation is of the following format—
T(n) = aT(n/b) + f(n) \quad \text{where} f(n) \in \Theta (n^d), d \ge 0
—we can use Master Theorem to quickly tell time efficiency.
Master Theorem:
T(n) T(n) = 4T(n/2) + n a=4; b=2; d=1 This falls into the third category. T(n) \in \Theta ( n^{\log_2^4} ) \\
\in \Theta (n^2) T(n) = 4T(n/2) + n^2 a=4; b=2; d=2 This falls into 2nd category. T(n) \in \Theta(n^d \log n) \\
\in Theta(n^2 \log n) T(n) = 4T(n/2) + n^3 a=4; b=2; d=3 This is first case. T(n) \in \Theta (n^d) \\
\in \Theta(n^3)Example: Applying master theorem.
This’ll be on the next exam!
Algorithm:
Splitting is easy, but how to you merge?
We only need to compare two elements when merging, because B and C are sorted.
mergesortmerge
As a recurrence relation, this is:
T(n) = 2T(n/2) + f(n)
Where f(n) is the merge operation
We know the recursive depth is \log n. In the worst case, we do n comparisons on each level.
Thus, we intuitively know we need at most O(n \log n) comparisons.
Now, let’s return to the master theorem solution.
We can say f(n) \in O(n)
Thus, a=2, b=2, d=1.
Thus, T(n)= \T(n \log n)
Tradeoff: Extra memory use.
Select a pivot. Rearrange the list so all element in first s positions are smaller than or equal to the pivot and all the element in the remaining n-s positions are \le the pivot.
TODO
TODO