Algorithms and Data Structures Recurrence Relations PDF
Document Details
Uploaded by HallowedEinstein
Technische Universität Hamburg-Harburg
2024
Matthias Mnich
Tags
Summary
This document is part of a lecture on algorithms and data structures related to recurrence relations, discussing a specific type of recurrence relation and its solution using induction, proving time complexity. The notes cover the concept of solving recurrence relations and analyzing time complexity, aiming to establish a relationship between input size and processing time.
Full Transcript
1 Algorithms and Data Structures Winter Term 2024/25 5th Lecture Recurrence Relations Prof. Dr. Matthias Mnich Institute for Algorithms and Complexity 2-1 Sol...
1 Algorithms and Data Structures Winter Term 2024/25 5th Lecture Recurrence Relations Prof. Dr. Matthias Mnich Institute for Algorithms and Complexity 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? 2-2 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. 2-3 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. 2-4 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. 2-5 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 2-6 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ 2-7 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. 2-8 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n 2-9 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · (log2 n − log2 2) + 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · (log2 n − log2 2) + 4n 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · (log2 n − log2 2) + 4n = cn log2 n − cn + 4n 2-1 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · (log2 n − log2 2) + 4n = cn log2 n − cn + 4n = cn log2 n + (4 − c )n 2-2 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · (log2 n − log2 2) + 4n = cn log2 n − cn + 4n = cn log2 n + (4 − c )n ≤ cn log2 n 2-2 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · (log2 n − log2 2) + 4n = cn log2 n − cn + 4n = cn log2 n + (4 − c )n ≤ cn log2 n if c ≥ 4. 2-2 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · (log2 n − log2 2) + 4n = cn log2 n − cn + 4n = cn log2 n + (4 − c )n ≤ cn log2 n if c ≥ 4. ⇒ Claim is true (there exists a c > 0...) 2-2 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · (log2 n − log2 2) + 4n = cn log2 n − cn + 4n = cn log2 n + (4 − c )n ≤ cn log2 n if c ≥ 4. ⇒ Claim is true (there exists a c > 0...) ⇒ T (n) ∈ O (n log n)! 2-2 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n ≤ 2c n2 log2 n2 + 4n (due to IH) = cn · (log2 n − log2 2) + 4n = cn log2 n − cn + 4n = cn log2 n + (4 − c )n ≤ cn log2 n if c ≥ 4. ⇒ Claim is true (there exists a c > 0...) ⇒ T (n) ∈ O (n log n)! Strictly speaking, we have only proven the claim when n is a power of two. The next slide will be more precise with this. 2-2 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n n n Substitution method: ≤ 2c 2 log 2 2 + 4n (due to IH) = cn · (log2 n − log2 2) + 4n = cn log2 n − cn + 4n = cn log2 n + (4 − c )n ≤ cn log2 n if c ≥ 4. ⇒ Claim is true (there exists a c > 0...) ⇒ T (n) ∈ O (n log n)! Strictly speaking, we have only proven the claim when n is a power of two. The next slide will be more precise with this. 2-2 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n n n Substitution method: ≤ 2c 2 log 2 2 + 4n (due to IH) 1. Guess a solution = cn · (log2 n − log2 2) + 4n of the recurrence = cn log2 n − cn + 4n = cn log2 n + (4 − c )n ≤ cn log2 n if c ≥ 4. ⇒ Claim is true (there exists a c > 0...) ⇒ T (n) ∈ O (n log n)! Strictly speaking, we have only proven the claim when n is a power of two. The next slide will be more precise with this. 2-2 Solving recurrence relations Question: Does T (n) = 2 · T (n/2) + 4n (with T (1) = 0) imply T (n) ∈ O (n log n) ? Claim: There exists a c > 0 such that T (n) ≤ cn log2 n. Proof. By induction over n. Base case: T (1) ≤ 0 ✓ IH: T (k ) ≤ ck log2 k holds for all k < n. We know: T (n) = 2T (n/2) + 4n n n Substitution method: ≤ 2c 2 log 2 2 + 4n (due to IH) 1. Guess a solution = cn · (log2 n − log2 2) + 4n of the recurrence = cn log2 n − cn + 4n 2. Prove it using = cn log2 n + (4 − c )n induction ≤ cn log2 n if c ≥ 4. ⇒ Claim is true (there exists a c > 0...) ⇒ T (n) ∈ O (n log n)! Strictly speaking, we have only proven the claim when n is a power of two. The next slide will be more precise with this. 3-1 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 (with T (1) = 0) 3-2 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) 3-3 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: 3-4 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. 3-5 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. 3-6 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. 3-7 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: 3-8 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck for all k < n. 3-9 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck for all k < n. We know: 3-1 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 3-1 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ c · ⌊n/2⌋ + c · ⌈n/2⌉ + 1 3-1 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ c · ⌊n/2⌋ + c · ⌈n/2⌉ + 1 by IH 3-1 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ c · ⌊n/2⌋ + c · ⌈n/2⌉ + 1 by IH ≤ c · ⌊n/2⌋ + ⌈n/2⌉ + 1 3-1 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ c · ⌊n/2⌋ + c · ⌈n/2⌉ + 1 by IH ≤ c · ⌊n/2⌋ + ⌈n/2⌉ + 1 ≤c ·n+1 3-1 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ c · ⌊n/2⌋ + c · ⌈n/2⌉ + 1 by IH ≤ c · ⌊n/2⌋ + ⌈n/2⌉ + 1 ≤c ·n+1 3-1 I) Substitution method Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We have to show: T (n) ≤ cn for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ c · ⌊n/2⌋ + c · ⌈n/2⌉ + 1 by IH ≤ c · ⌊n/2⌋ + ⌈n/2⌉ + 1 ≤c ·n+1 4-1 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. 4-2 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. 4-3 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. Induction over n. 4-4 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. Induction over n. IH: 4-5 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck + 1 for all k < n. 4-6 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck + 1 for all k < n. We know: 4-7 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck + 1 for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 4-8 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck + 1 for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c · ⌊n/2⌋ + 1) + (c · ⌈n/2⌉ + 1) + 1 4-9 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck + 1 for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c · ⌊n/2⌋ + 1) + (c · ⌈n/2⌉ + 1) + 1 ≤c ·n+3 4-1 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck + 1 for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c · ⌊n/2⌋ + 1) + (c · ⌈n/2⌉ + 1) + 1 ≤c ·n+3 4-1 Another attempt Another example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) We instead show: T (n) ≤ cn + 1 for a constant c > 0. Proof. Induction over n. IH: T (k ) ≤ ck + 1 for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c · ⌊n/2⌋ + 1) + (c · ⌈n/2⌉ + 1) + 1 ≤c ·n+3 5-1 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: 5-2 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. 5-3 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! 5-4 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! Proof. Induction over n. 5-5 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. 5-6 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 5-7 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c ⌊n/2⌋ − d ) + (c ⌈n/2⌉ − d ) + 1 5-8 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c ⌊n/2⌋ − d ) + (c ⌈n/2⌉ − d ) + 1 ≤ c · ⌊n/2⌋ + ⌈n/2⌉ − d − d + 1 5-9 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c ⌊n/2⌋ − d ) + (c ⌈n/2⌉ − d ) + 1 ≤ c · ⌊n/2⌋ + ⌈n/2⌉ − d − d + 1 ≤ cn − d + (1 − d ) 5-1 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c ⌊n/2⌋ − d ) + (c ⌈n/2⌉ − d ) + 1 ≤ c · ⌊n/2⌋ + ⌈n/2⌉ − d − d + 1 ≤ cn − d + (1 − d ) ≤ cn − d 5-1 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c ⌊n/2⌋ − d ) + (c ⌈n/2⌉ − d ) + 1 ≤ c · ⌊n/2⌋ + ⌈n/2⌉ − d − d + 1 ≤ cn − d + (1 − d ) ≤ cn − d if d ≥ 1. 5-1 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c ⌊n/2⌋ − d ) + (c ⌈n/2⌉ − d ) + 1 ≤ c · ⌊n/2⌋ + ⌈n/2⌉ − d − d + 1 ≤ cn − d + (1 − d ) ≤ cn − d if d ≥ 1. ✓ 5-1 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. ✓ I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c ⌊n/2⌋ − d ) + (c ⌈n/2⌉ − d ) + 1 ≤ c · ⌊n/2⌋ + ⌈n/2⌉ − d − d + 1 ≤ cn − d + (1 − d ) ≤ cn − d if d ≥ 1. ✓ 5-1 Don’t despair! Same example: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 Claim: T (n ) ∈ O (n ) ✓ (with T (1) = 0) Now we attempt: T (n) ≤ cn − d for constants c , d > 0. ✓ I.e. we make our claim tighter!! Proof. Induction over n. IH: T (k ) ≤ ck − d for all k < n. We know: T (n) = T (⌊n/2⌋) + T (⌈n/2⌉) + 1 ≤ (c ⌊n/2⌋ − d ) + (c ⌈n/2⌉ − d ) + 1 ≤ c · ⌊n/2⌋ + ⌈n/2⌉ − d − d + 1 ≤ cn − d + (1 − d ) ≤ cn − d if d ≥ 1. ✓ 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (with T (1) = 1) 6-2 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (with T (1) = 1) T (n) 6-3 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (with T (1) = 1) T (n) 6-4 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (with T (1) = 1) T (n) 6-5 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (with T (1) = 1) T (n) n2 6-6 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (with T (1) = 1) T (n) n2 6-7 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 6-8 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 6-9 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 (∗) 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 (∗) n 2 4 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 (∗) n 2 4 n n n T 16 T 16 T 16 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 (∗) n 2 4 n n n T 16 T 16 T 16 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 (∗) n 2 n 2 4 4 n n n n n n T 16 T 16 T 16 T 16 T 16 T 16 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 (∗) n 2 n 2 4 4 n n n n n n T 16 T 16 T 16 T 16 T 16 T 16 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 (∗) n 2 n 2 n 2 4 4 4 n n n n n n n n n T 16 T 16 T 16 T 16 T 16 T 16 T 16 T 16 T 16 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 n 2 n 2 n 2 4 4 4 n n n n n n n n n T 16 T 16 T 16 T 16 T 16 T 16 T 16 T 16 T 16 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 n 2 n 2 n 2 4 4 4 n n n n n n n n n T 16 T 16 T 16 T 16 T 16 T 16 T 16 T 16 T 16 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 n 2 n 2 n 2 4 4 4 n n2 n n n n n n n n T 1616 T 16 T 16 T 16 T 16 T 16 T 16 T 16 T 16 6-1 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 n 2 n 2 n 2 4 4 4 n n2 n n2 n n2 n n2 n n2 n n2 n n2 n n2 n n2 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 6-2 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 n 2 n 2 n 2 4 4 4 n n2 n n2 n n2 n n2 n n2 n n2 n n2 n n2 n n2 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616......... 6-2 II) Recursion tree method Example: T (n) = 3T (n/4) + n2 (∗) (with T (1) = 1) T (n) n2 n n n T 4 T 4 T 4 n2 n 2 n 2 n 2 4 4 4 n n2 n n2 n n2 n n2 n n2 n n2 n n2 n n2 n n2 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616 T 1616......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-1 II) Recursion tree method T (n) = 3T (n/4) + n2n2 n 2 n 2 n 2 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 n 2 n 2 n 2 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-3 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 n 2 n 2 n 2 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-4 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n 2 n 2 n 2 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-5 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 n 2 n 2 n 2 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-6 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 n 2 n 2 n 2 1 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-7 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 n 2 n 2 n 2 1 31 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-8 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-9 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............ i T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2 T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2...... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2...... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n = 7-1 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2...... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n = nlog4 3 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n nlog4 3 = nlog4 3 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n nlog4 3 = given that nlog4 3 T (1) = 1 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n nlog4 3 = given that nlog4 3 T (1) = 1 ⇒ T (n ) = 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n nlog4 3 = given that bottom layer other layers nlog4 3 T (1) = 1 ⇒ T (n ) = + 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n nlog4 3 = given that bottom layer other layers nlog4 3 T (1) = 1 ⇒ T (n) = nlog4 3 + 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n nlog4 3 = given that bottom layer other layers nlog4 3 T (1) = 1 (log4 n)−1 X i ⇒ T (n) = nlog4 3 + 3 16 n2 ≤ i =0 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n nlog4 3 = given that bottom layer other layers nlog4 3 T (1) = 1 (log4 n)−1 X i ⇒ T (n) = nlog4 3 + 3 16 n2 ≤ n0,793 + i =0 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n nlog4 3 = given that bottom layer other layers nlog4 3 T (1) = 1 (log4 n)−1 log4 3 X i 3 2 0,793 2 P∞ 3 i ⇒ T (n ) = n + 16 n ≤n +n i =0 16 = i =0 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n 16 16 16 16 16 16 16 16 16............... i 3i... i 3 16i n2......... T (1) T (1) T (1) T (1) T (1) T (1) T (1)... T (1) T (1) T (1) T (1) T (1) T (1) T (1) log4 n 3log4 n nlog4 3 = given that bottom layer other layers nlog4 3 T (1) = 1 (log4 n)−1 log4 3 X i 3 2 0,793 2 P∞ 3 i ⇒ T (n ) = n + 16 n ≤n +n i =0 16 = i =0 7-2 II) Recursion tree method Layer Node Impact count (Layer) T (n) = 3T (n/4) + n2n2 0 30 = 1 n2 3 2 n 2 n 2 n 2 1 31 16 n 4 4 4 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 n 2 2 32 2 2 3 162 n
