Algorithms and Data Structures Lecture Notes (Winter 2024/25) PDF

1 Algorithms and Data Structures Winter Term 2024/25 3rd Lecture Run Time Analysis Prof. Dr. Matthias Mnich Institute for Algorithms and Complexity ...

1 Algorithms and Data Structures Winter Term 2024/25 3rd Lecture Run Time Analysis Prof. Dr. Matthias Mnich Institute for Algorithms and Complexity  2 Recap: Discuss with your neighbour! 1. What are the two (or three?) most important questions which we ask ourselves about an algorithm? 2. Why do we even care about sorting? 3. Which design techniques for algorithms do we already know? Did for you al 4. e r How do we prove the correctness of – In xamp eady i le mp – M sertion , lem ent a) a loop? Try ergeSo Sort, , it y r our t,... ? self b) an incremental algorithm? ! c) a recursive algorithm?  3-1 Run time analysis: InsertionSort InsertionSort(int[ ] A) for j = 2 to A.length do key = A[j ] i =j −1 while i > 0 and A[i ] > key do A[i + 1] = A[i ] i =i −1 A[i + 1] = key  3-2 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] i =j −1 while i > 0 and A[i ] > key do A[i + 1] = A[i ] i =i −1 A[i + 1] = key  3-3 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do A[i + 1] = A[i ] i =i −1 A[i + 1] = key  3-4 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 A[i + 1] = key  3-5 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key  3-6 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input)  3-7 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input)  3-8 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input) Goal: Measure for the run time, depending only on n.  3-9 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input) Goal: Measure for the run time, depending only on n. Problem: Actual run time is highly dependent on input.  3-1 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input) Goal: Measure for the run time, depending only on n. Problem: Actual run time is highly dependent on input. Solution(?):Consider extreme cases!  3-1 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input) Goal: Measure for the run time, depending only on n. Problem: Actual run time is highly dependent on input. Solution(?):Consider extreme cases! Best case: Worst case:  3-1 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input) Goal: Measure for the run time, depending only on n. Problem: Actual run time is highly dependent on input. Solution(?):Consider extreme cases! Best case: A already sorted Worst case:  3-1 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input) Goal: Measure for the run time, depending only on n. Problem: Actual run time is highly dependent on input. Solution(?):Consider extreme cases! Best case: A already sorted ⇒ n − 1 comparisons Worst case:  3-1 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input) Goal: Measure for the run time, depending only on n. Problem: Actual run time is highly dependent on input. Solution(?):Consider extreme cases! Best case: A already sorted ⇒ n − 1 comparisons Worst case: A sorted descendingly  3-1 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input) Goal: Measure for the run time, depending only on n. Problem: Actual run time is highly dependent on input. Solution(?):Consider extreme cases! Best case: A already sorted ⇒ n − 1 comparisons Worst case: A sorted descendingly ⇒ 1 + 2 + · · · + (n − 1) =  3-1 Run time analysis: InsertionSort InsertionSort(int[ ] A) Two conventions: for j = 2 to A.length do key = A[j ] 1) n := size of the input i =j −1 while i > 0 and A[i ] > key do =here A.length A[i + 1] = A[i ] i =i −1 2) We only count comparisons! A[i + 1] = key (between elements of the input) Goal: Measure for the run time, depending only on n. Problem: Actual run time is highly dependent on input. Solution(?):Consider extreme cases! Solution(?): Best case: A already sorted ⇒ n − 1 comparisons Worst case: A sorted descendingly n2 − n ⇒ 1 + 2 + · · · + (n − 1) = compar. 2  4-1 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine  4-2 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine  4-3 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Efficient?  4-4 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Efficient? Let CMS (n) be the maximum number of comparisons which MergeSort needs to sort n numbers.  4-5 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Efficient? Let CMS (n) be the maximum number of comparisons which MergeSort needs to sort n numbers. Then it holds ( 0 if n = 1, CMS (n) = 2CMS (n/2) + n otherwise  4-6 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Efficient? Let CMS (n) be the maximum number of comparisons which MergeSort needs to sort n numbers. Then it holds ( 0 if n = 1, CMS (n) = 2CMS (n/2) + n otherwise  4-7 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Efficient? Let CMS (n) be the maximum number of comparisons which MergeSort needs to sort n numbers. Then it holds ( 0 if n = 1, CMS (n) = 2CMS (n/2) + n otherwise  4-8 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Efficient? Let CMS (n) be the maximum number of comparisons which MergeSort needs to sort n numbers. Then it holds ( 0 if n = 1, CMS (n) = 2CMS (n/2) + n otherwise  4-9 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Efficient? Let CMS (n) be the maximum number of comparisons which MergeSort needs to sort n numbers. Then it holds ( ) 0 if n = 1, CMS (n) = = n log2 n 2CMS (n/2) + n otherwise  4-1 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Efficient? Let CMS (n) be the maximum number of comparisons which MergeSort needs to sort n numbers. Then it holds ( ) 0 if n = 1, CMS (n) = = n log2 n 2CMS (n/2) + n otherwise if n is a power of two  4-1 Run time of MergeSort MergeSort(int[ ] A, int ℓ = 1, int r = A.length) if ℓ < r then m = ⌊(ℓ + r )/2⌋ } divide MergeSort(A, ℓ, m) Correct? MergeSort(A, m + 1, r ) } conquer Merge(A, ℓ, m, r ) } combine Efficient? Let CMS (n) be the maximum number of comparisons which MergeSort needs to sort n numbers. Then it holds ( ) 0 if n = 1, CMS (n) = = n log2 n 2CMS (n/2) + n otherwise if n is a power of two  5-1 Comparison InsertionSort vs. MergeSort 16 14 12 10 8 MergeSort: CMS (x ) = x log2 x 6 InsertionSort: x2 − x 4 CIS (x ) = 2 2 0 1 2 3 4 5 6  5-2 Comparison InsertionSort vs. MergeSort 16 14 12 10 8 MergeSort: CMS (x ) = x log2 x 6 InsertionSort: x2 − x 4 CIS (x ) = 2 2 0 1 2 3 4 5 6  5-3 Comparison InsertionSort vs. MergeSort 16 14 12 10 8 MergeSort: CMS (x ) = x log2 x 6 InsertionSort: x2 − x 4 CIS (x ) = 2 2 0 1 2 3 4 5 6  6 Comparison InsertionSort vs. MergeSort 5000 4500 4000 3500 3000 2500 x2 − x CIS (x ) = 2 2000 1500 1000 CMS (x ) = x log2 x 500 0 10 20 30 40 50 60 70 80 90 100  7-1 A classification scheme for functions (I) Definition. Let g : N → R be a function.  7-2 A classification scheme for functions (I) Definition. Let g : N → R be a function. 2 √ Set of real numers, e.g. −7, 3, 9, 2, e , π 2. Set of natural numbers 0, 1, 2,...  7-3 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g.  7-4 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g.  7-5 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20  7-6 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n 2 )  7-7 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically.  7-8 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. Proof. Choose positive c and n0 ,  7-9 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2.  7-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2.  7-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2. f (n) = 2n2 + 4n − 20 ≤  7-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2. f (n) = 2n2 + 4n − 20 ≤ 6n2  7-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. as 4n ≤ 4n2 Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2. f (n) = 2n2 + 4n − 20 ≤ 6n2  7-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. as 4n ≤ 4n2 Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2. f (n) = 2n2 + 4n − 20 ≤ 6n2 ⇒  7-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. as 4n ≤ 4n2 Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2. f (n) = 2n2 + 4n − 20 ≤ 6n2 ⇒ choose c = 6.  7-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. as 4n ≤ 4n2 Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2. f (n) = 2n2 + 4n − 20 ≤ 6n2 ⇒ choose c = 6. Which n0 ?  7-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. as 4n ≤ 4n2 Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2. f (n) = 2n2 + 4n − 20 ≤ 6n2 ⇒ choose c = 6. Which n0 ? Statement holds for all n ≥ 0.  7-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ∈ O (n2 ); i.e. f grows at most quadratically. as 4n ≤ 4n2 Proof. Choose positive c and n0 , such that for all n ≥ n0 it holds: f (n) ≤ c · n2. f (n) = 2n2 + 4n − 20 ≤ 6n2 ⇒ choose c = 6. Which n0 ? Statement holds for all n ≥ 0. E.g. pick n0 = 1. □  8-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ̸∈ O (n)  8-2 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly.  8-3 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show:  8-4 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show:  8-5 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 negate! ( ¬) Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show:  8-6 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 negate! ( ¬) Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show:  8-7 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 negate! ( ¬) Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show: for all pos. const. c and n0  8-8 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 negate! ( ¬) Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show: for all pos. const. c and n0  8-9 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 negate! ( ¬) Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show: for all pos. const. c and n0 there is a n ≥ n0 ,  8-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 negate! ( ¬) Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show: for all pos. const. c and n0 there is a n ≥ n0 ,  8-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 negate! ( ¬) Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show: for all pos. const. c and n0 there is a n ≥ n0 , such that f (n) > c · n.  8-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show: for all pos. const. c and n0 there is a n ≥ n0 , such that f (n) > c · n.  8-1 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g. Example. f (n) = 2n2 + 4n − 20 Claim.: f ̸∈ O (n) ; i.e. f grows faster than linearly. Proof. Show: for all pos. const. c and n0 there is a n ≥ n0 , such that f (n) > c · n. Therefore: determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n.  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n.  9-2 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ”  9-3 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then...  9-4 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0.  9-5 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0.  9-6 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then...  9-7 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn.  9-8 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕  9-9 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑ How about n=c ?  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑ How about n=c ? Good, but...  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑ How about n=c ? Good, but...  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑ How about n=c ? Good, but we need to ensure that additionally n ≥ 5 and n ≥ n0 hold.  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑ How about n=c ? Good, but we need to ensure that additionally n ≥ 5 and n ≥ n0 hold. Consequently, we take n =  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑ How about n=c ? Good, but we need to ensure that additionally n ≥ 5 and n ≥ n0 hold. Consequently, we take n =⌈max(c , 5, n0 )⌉.  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑ How about n=c ? Good, but we need to ensure that additionally n ≥ 5 and n ≥ n0 hold. Consequently, we take n =⌈max(c , 5, n0 )⌉. For this n it holds n ≥ n0 and f (n) > cn.  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑ How about n=c ? Good, but we need to ensure that additionally n ≥ 5 and n ≥ n0 hold. Consequently, we take n =⌈max(c , 5, n0 )⌉. For this n it holds n ≥ n0 and f (n) > cn.  9-1 Continuation of the proof of f ̸∈ O(n) Determine n for given c and n0 , such that n ≥ n0 and f (n) = 2n2 + 4n − 20 > c · n. Problem: The −20“ is interfering. ” But if n ≥ 5, then it holds that 4n − 20 ≥ 0. I.e. if n ≥ 5 and 2n2 > cn, then f (n) > cn. ⇕ n > c /2 ⇑ How about n=c ? Good, but we need to ensure that additionally n ≥ 5 and n ≥ n0 hold. Consequently, we take n =⌈max(c , 5, n0 )⌉. For this n it holds n ≥ n0 and f (n) > cn. Hence, f ̸∈ O (n). □  10 A classification scheme for functions (I) Definition. Let g : N→ R be a function. Then Big-Oh of g “ is ”   there are positive constants c and n0 ,  O (g ) = f : N → R | such that for all n ≥ n0 it holds that: f (n) ≤ c · g (n)   i.e. the class of function which grow at most as quickly as g.  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g.  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 )  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 )  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 ) Consequently:  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 ) Consequently: f ∈ Ω (n)  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 ) Consequently: f ∈ Ω (n) , f ∈ Ω (n2 )  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 ) Consequently: f ∈ Ω (n) , f ∈ Ω (n2 ) , f ̸∈ Ω (n3 )  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 ) Consequently: f ∈ Ω (n) , f ∈ Ω (n2 ) , f ̸∈ Ω (n3 )  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 ) Consequently: f ∈ Ω (n) , f ∈ Ω (n2 ) , f ̸∈ Ω (n3 ) Together:  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 ) Consequently: f ∈ Ω (n) , f ∈ Ω (n2 ) , f ̸∈ Ω (n3 ) Together: f ∈ Θ (n 2 )  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 ) Consequently: f ∈ Ω (n) , f ∈ Ω (n2 ) , f ̸∈ Ω (n3 ) Together: f ∈ Θ (n 2 ) i.e. there are pos. const. c1 , c2 , n0 s.t. for all n ≥ n0 it holds  11 - A classification scheme for functions (II) Definition. Let g : N→ R be a function. Then Big-Omega of g “ is ”   there are positive constants c and n0 ,  Ω (g ) = f : N → R | such that for all n ≥ n0 it holds that: c · g (n) ≤ f (n)   i.e. the class of function which grow at least as quickly as g. Example. f (n) = 2n2 + 4n − 20 Proved: f ̸∈ O (n) , f ∈ O (n2 ) , f ∈ O (n3 ) Consequently: f ∈ Ω (n) , f ∈ Ω (n2 ) , f ̸∈ Ω (n3 ) Together: f ∈ Θ (n 2 ) i.e. there are pos. const. c1 , c2 , n0 s.t. for all n ≥ n0 it holds c1 · n2 ≤ f (n) ≤ c2 · n2.  12 - The classification scheme – intuitively f ∈ O (n2 ) means  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically.  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 )  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least f ∈ Θ (n 2 )  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least f ∈ Θ (n 2 ) exactly“ ”  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least f ∈ Θ (n 2 ) exactly“ ” f ∈ o (n 2 ) new!  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least f ∈ Θ (n 2 ) exactly“ ” f ∈ o (n 2 ) strictly slower than new!  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least f ∈ Θ (n 2 ) exactly“ ” f ∈ o (n 2 ) strictly slower than 2 new! f ∈ ω(n )  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least f ∈ Θ (n 2 ) exactly“ ” f ∈ o (n 2 ) strictly slower than 2 new! f ∈ ω(n ) strictly faster than  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least f ∈ Θ (n 2 ) exactly“ ” f ∈ o (n 2 ) strictly slower than 2 new! f ∈ ω(n ) strictly faster than For exact definitions of small-Oh“ and small-Omega“, see Ch. 3, [CLRS]. ” ”  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least f ∈ Θ (n 2 ) exactly“ ” f ∈ o (n 2 ) strictly slower than 2 new! f ∈ ω(n ) strictly faster than For exact definitions of small-Oh“ and small-Omega“, see Ch. 3, [CLRS]. ” ” Exercise. Consider the following functions N → R with n 7→... : 2 p n , log2 n, n log2 n, 1.01n , nlog3 4 , log2 (n · 2n ), 4log3 n.  12 - The classification scheme – intuitively f ∈ O (n2 ) means f grows at most quadratically. f ∈ Ω (n 2 ) at least f ∈ Θ (n 2 ) exactly“ ” f ∈ o (n 2 ) strictly slower than 2 new! f ∈ ω(n ) strictly faster than For exact definitions of small-Oh“ and small-Omega“, see Ch. 3, [CLRS]. ” ” Exercise. Consider the following functions N → R with n 7→... : 2 p n , log2 n, n log2 n, 1.01n , nlog3 4 , log2 (n · 2n ), 4log3 n. Sort them by their speed of asymptotic growth, i.e. build a chain of the form: O (... ) ⊆ O (... ) ⊆ · · · ⊆ O (... ).