Algorithms Design Implementation - Lecture3

9th April 2023

Lecture # 3: Outline 1 Recap of Previous Lecture 2 Master Method 2 / 14

Recurrence Relation Recurrence relation: An equation/inequality that describes a function in terms of its value. Standard recurrence format: T (n) = aT n + O(nd ) b a: number of recursive calls/ number of subproblems b: factor by which input size shrinks d: the exponent of n in the time it takes to generate the subproblems and combine their solutions. n : size of subproblems b O(nd ): local cost at node 3 / 14

Geometric Series  = a(r n −1) , if r > 1 Sn = r −1 if r < 1  a(1−r n ) if 0 < r < 1 sum Sn 1−r , S∞ = a , 1−r Logarithms logban = nlogba  log  = logc a logba logc b logba = 1 logab  alogbc = clogba 4 / 14

Methods 1. Iteration Method: simply iterate until initial condition met 2. Recursion Tree Method Recursion Tree: K a node represents the cost of single subproblem K cost at a level is the sum of the cost of each node at that level K total cost is sum of the cost of each level 3. Master Method 5 / 14

Recursion Tree Method Example: T (n) = 2T (n/2) + n2 level size cost of # of cost per subprob one node 1 level 2 0n n2 4 n2 1 n n2 2k 2 n2 2 4 4 n2 n2 2 n 16 8 64 4 ··· k 1 = n 2k n2 2k n2 22k 22k k = log2 n 6 / 14

Recursion Tree Method k = log2 n sum = n2 + n2/2 + n2/4 + ....+ up to kth term a = n2 r = 1/2 < 1; total k + 1 terms 7 / 14

Recursion Tree Method T (n) = T (n/3) + T (2n/3) + cn [≤ cnlog3/2n = θ(nlog3/2n)] Longest path?? 8 / 14

upshots 1. Halves problem in constant time T (n) = T ( n ) + c =⇒ θ(logn) 2 2. Halves problem in linear time T (n) = T ( n ) + n =⇒ θ(n) 2 3. Break the problem in two halves in constant time T (n) = 2T ( n ) + c =⇒ θ(n) 2 4. Break the problem in two halves in linear time T (n) = T ( n ) + n =⇒ θ(nlogn) 2 5. Reduce the problem by one in constant time T (n) = T (n − 1) + c =⇒ θ(n) 6. Reduce the problem by one in linear time T (n) = T (n − 1) + n =⇒ θ(n2) 9 / 14

Master Methods A formula for many recurrence relations Standard recurrence format: T (n) = aT n + O(nd ) b a ≥ 1, b > 1, d ≥ 0 O(nd logn), ifa = bd  ifa < bd T (n) = O(nd ), ifa > bd O (nlogb a ), T (n) = 4T (n/2) + O(n2) T (n) = 34T (n/4) + cn2 T (n) = 2T (n/2) + O(n2) T (n) = 3T (n/2) + O(n) 10 / 14

Why it works T (n) = aT n + O(nd ) b a ≥ 1, b > 1, d ≥ 0 level size cost of # of cost per subprob one node 1 level a 0n cnd a2 cnd 1 n c( n )d ak ac( n )d b b b n n )d a2 n )d 2 b2 c ( b2 c ( b2 ··· k 1 = n c( n )d ak c ( n )d bk bk bk 11 / 14

Why it works 12 / 14

Why it works 13 / 14

Thanks.