How to solve/bound this recurrence relation? ■T(n)≤2T(n/2)+c·n ≤2T(m/4)+c·n/2 ≤4T(n/4)+2c·n ≤2T(n/8)+c·n/4 ≤8T(m/8)+3c·n ≤ ≤nT(n/m)+(ogn)c·n ≤O(n logn): 6
How to solve/bound this recurrence relation? ◼ 𝑇 𝑛 ≤ 2𝑇 𝑛/2 + 𝑐 ⋅ 𝑛 ~~~~~~~~ ≤ 2𝑇(𝑛/4) + 𝑐 ∙ 𝑛/2 ≤ 4𝑇(𝑛/4) + 2𝑐 ∙ 𝑛 ~~~~~~~ ≤ 2𝑇(𝑛/8) + 𝑐 ∙ 𝑛/4 ≤ 8𝑇(𝑛/8) + 3𝑐 ∙ 𝑛 ≤ … ≤ 𝑛𝑇(𝑛/𝑛) + (log 𝑛)𝑐 ∙ 𝑛 ≤ 𝑂(𝑛 log 𝑛). 6
A general method for designing algorithm: Divide and conquer o f Breaking the problem into subproblems that are themselves smaller instances of the same type of problem Recursively solving these subproblems Appropriately combining their answers
A general method for designing algorithm: Divide and conquer ◼ Breaking the problem into subproblems ❑ that are themselves smaller instances of the same type of problem ◼ Recursively solving these subproblems ◼ Appropriately combining their answers 7
Complexity Running time on an input of size n:T(n) Break problem into a subproblems,each of the same size n/b. In general,a is not necessarily equal to b. Time to recursively solve each subproblem: T(n/b) Time for breaking problem (into subproblems) and combining the answers:0(n) 8
Complexity ◼ Running time on an input of size 𝑛: 𝑇(𝑛) ◼ Break problem into 𝑎 subproblems, each of the same size 𝑛/𝑏. ❑ In general, 𝑎 is not necessarily equal to 𝑏. ◼ Time to recursively solve each subproblem: 𝑇(𝑛/𝑏) ◼ Time for breaking problem (into subproblems) and combining the answers: 𝑂(𝑛 𝑑 ) 8
Master theorem ·T(n)=aT(n/b)+O(na) a 0,b>1,and d >0 are all constants. Then O(n m了O3 ifd logb a O(ndlogn) if d logb a ifd<logb a· Proof in textbook.Not required. 口 But you need to know how to apply it. 9
Master theorem ◼ 𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑂(𝑛 𝑑 ) ❑ 𝑎 > 0, 𝑏 > 1, and 𝑑 ≥ 0 are all constants. ◼ Then ❑ Proof in textbook. Not required. ❑ But you need to know how to apply it. 9
■T(n)=aT(n/b)+O(nd) rm二z ifd logb a O(ndlogn) if d logb a if'd logb a. Merge sort:T(n)<2T(n/2)+0(n). a=b=2,d=1.So d=logb a. By the master theorem:T(n)=0(n logn). 10
◼ 𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑂(𝑛 𝑑 ) ◼ Merge sort: 𝑇(𝑛) ≤ 2𝑇(𝑛/2) + 𝑂(𝑛). ◼ 𝑎 = 𝑏 = 2, 𝑑 = 1. So 𝑑 = log𝑏 𝑎. ◼ By the master theorem: 𝑇(𝑛) = 𝑂(𝑛 log 𝑛). 10