Algorithms Design Implementation - Lecture 2

8th April 2023

Lecture # 2: Outline 1 Recap of Previous Lecture 2 Recurrence Relation 3 Methods for Solving Recurrence Relations 2 / 16

Asymptotic Analysis K Framework for classifying the behavior of functions K Our motive is to differentiate two solutions (algorithms) for a problem in terms of efficiency Features: 1. Constant multiplier should be ignored, i.e., 5n2 + 2n + 3 and 100n2 + 45 should belong to same class 2. Determine behavior when n =⇒ ∞ 3 / 16

Asymptotic Notations K Big-O notation: O(f (n)) = {T (n)|∃c > 0, n0 ≥ 0, s.t. T (n) ≤ cf (n), ∀n ≥ n0} K Big-Ω notation: Ω(f (n)) = {T (n)|∃c > 0, n0 ≥ 0, s.t. T (n) ≥ cf (n), ∀n ≥ n0} K Big-θ notation: θ(f (n)) = {T (n)|∃c1, c2 > 0, n0 ≥ 0, s.t. c1f (n) ≤ T (n) ≤ c2f (n), ∀n ≥ n0} 4 / 16

Asymptotic Notations: summarization K T (n) ∈ O(f (n)) T (n) is no greater than f (n), i.e., ≤ K T (n) ∈ O(f (n)) T (n) is no smaller than f (n), i.e., ≥ K T (n) ∈ O(f (n)) T (n) is nearly same as f (n), i.e., = upshot: Lemma Let f (n) and g(n) denote functions from the positive integers to the non negative real numbers, and define T (n) = max{f (n), g(n)}for eachn, Then T (n) = θ(f (n) + g(n)). 5 / 16

Time Complexity Rules: 1. For loop: running time of statements inside the for loop times length of the loop (number of iterations) 1 for i ← 1 to n do 2 do some O(1) operation 3 end 2. Nested for loop: total running time of a statement inside a group of loops is running time of statement multiplied by the product of size of all for loops 1 for i ← 1 to n do 2 for j ← 1 to n do 3 do some O(1) operation 4 end 5 end 3. Consecutive statements: add them, i.e., find the maximum 1 if condition then 2 S1 3 else 4 S2 5 end 6 / 16

Examples 1 for (i = n/2; i ≤ n; i + +) do 2 for (j = 1; j + n/2 ≤ n; i + +) do 1 for (i = 1; i ∗ i ≤ n; i + +) do 3 for (k = 1; k ≤ n; k = 2 ∗ k ) do 2 k = k+1 4 l = l+1 3 end 5 end 6 end 7 end 7 / 16

Recurrence Relation Algorithm 1: f(n) Algorithm 2: Karatsuba Method: f(x,y) 1 if n ≤ 1 then 2 return n 1 if n = 1 then 3 else 2 compute x * y in one step 4 return f(n-1)+f(n-2) 3 else 5 end 4 a, b := first and second halves of x 5 c, d := first and second halves of y Which rule?? T(n) = T(n-1)+T(n-2)+2 compute f(a,c) 6 compute f(a,d) 7 compute f(b,c) 8 compute f(b,d) 9 compute 10nac + 10n/2(ad + bc) + bd 10 end T(n) = 4T(n/2)+O(n) 8 / 16

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 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. 9 / 16

Methods 1. Iteration Method 2. Recursion Tree Method 3. Master Method 10 / 16

Iteration Method Convert the recurrence into summation and try to bound it into a summation and try to bound it using known series K iterate the recurrence until initial condition meet K express recurrence in terms of n and initial condition Example: T (n) = c1, if n = 0 T (n − 1) + c2, otherwise 11 / 16

Iteration Method: Example T (n) = c1, if n = 1 T (n/2) + c2, otherwise 12 / 16

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 Example: T(n) = 2T(n/2)+n 13 / 16

Recursion Tree Method 14 / 16

Recursion Tree Method Example: T (n) = 2T (n/2) + n2 15 / 16

Recursion Tree Method 16 / 16

Thanks.