Divide and conquer Note:though there are two subproblems (of sizes SL|and SR),we need to solve only one of them. Compare:in quicksort,we need to sort both substrings！ Complexity: T(n)=max{T(SLD),T(SR)+0(n) A new issue:S and SR are not determined Depends on the pivot. 16
Divide and conquer ◼ Note: though there are two subproblems (of sizes |𝑆𝐿 | and |𝑆𝑅|), we need to solve only one of them. ❑ Compare: in quicksort, we need to sort both substrings! ◼ Complexity: 𝑇(𝑛) = max{𝑇(|𝑆𝐿 |),𝑇(|𝑆𝑅|)} + 𝑂(𝑛) ◼ A new issue: |𝑆𝐿 | and |𝑆𝑅| are not determined ❑ Depends on the pivot. 16
If the pivot is the median: ▣T(n)=T(n/2)+0(n) 口T(n)=aT(n/b)+0(nd) O(n4) dm=0%线g if'd logb a O(ndlogn) if d logb a ifd<logb a· o Thus finally T(n)=0(n),better than 0(nlogn)by sorting. 17
◼ If the pivot is the median: ❑ 𝑇(𝑛) = 𝑇(𝑛/2) + 𝑂(𝑛) ❑ 𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑂(𝑛 𝑑 ) ❑ Thus finally 𝑇(𝑛) = 𝑂(𝑛), better than 𝑂(𝑛log𝑛) by sorting. 17
If the pivot is at one end (say,the smallest) ▣T(n)=T(n-1)+0(n) What's the complexity? Complexity:0(n2) 18
◼ If the pivot is at one end (say, the smallest) ❑ 𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑂(𝑛) ❑ What’s the complexity? ❑ Complexity: 𝑂(𝑛 2 ) 18