Recursion tree method

Recursion tree method

• 1.
  Analysis of Algorithms CS477/677 Recurrences Instructor: George Bebis (Appendix A, Chapter 4)
• 2.
  2 Recurrences and RunningTime • An equation or inequality that describes a function in terms of its value on smaller inputs. T(n) = T(n-1) + n • Recurrences arise when an algorithm contains recursive calls to itself • What is the actual running time of the algorithm? • Need to solve the recurrence – Find an explicit formula of the expression – Bound the recurrence by an expression that involves n
• 3.
  3 Example Recurrences • T(n)= T(n-1) + n Θ(n2 ) – Recursive algorithm that loops through the input to eliminate one item • T(n) = T(n/2) + c Θ(lgn) – Recursive algorithm that halves the input in one step • T(n) = T(n/2) + n Θ(n) – Recursive algorithm that halves the input but must examine every item in the input • T(n) = 2T(n/2) + 1 Θ(n) – Recursive algorithm that splits the input into 2 halves and does a constant amount of other work
• 4.
  4 Recurrent Algorithms BINARY-SEARCH • foran ordered array A, finds if x is in the array A[lo…hi] Alg.: BINARY-SEARCH (A, lo, hi, x) if (lo > hi) return FALSE mid ← (lo+hi)/2 if x = A[mid] return TRUE if ( x < A[mid] ) BINARY-SEARCH (A, lo, mid-1, x) if ( x > A[mid] ) BINARY-SEARCH (A, mid+1, hi, x) 12111097532 1 2 3 4 5 6 7 8 mid lo hi
• 5.
  5 Example • A[8] ={1, 2, 3, 4, 5, 7, 9, 11} – lo = 1 hi = 8 x = 7 mid = 4, lo = 5, hi = 8 mid = 6, A[mid] = x Found!119754321 119754321 1 2 3 4 5 6 7 8 8765
• 6.
  6 Another Example • A[8]= {1, 2, 3, 4, 5, 7, 9, 11} – lo = 1 hi = 8 x = 6 mid = 4, lo = 5, hi = 8 mid = 6, A[6] = 7, lo = 5, hi = 5119754321 119754321 1 2 3 4 5 6 7 8 119754321 mid = 5, A[5] = 5, lo = 6, hi = 5 NOT FOUND! 119754321 low high low lowhigh high
• 7.
  7 Analysis of BINARY-SEARCH Alg.:BINARY-SEARCH (A, lo, hi, x) if (lo > hi) return FALSE mid ← (lo+hi)/2 if x = A[mid] return TRUE if ( x < A[mid] ) BINARY-SEARCH (A, lo, mid-1, x) if ( x > A[mid] ) BINARY-SEARCH (A, mid+1, hi, x) • T(n) = c + – T(n) – running time for an array of size n constant time: c2 same problem of size n/2 same problem of size n/2 constant time: c1 constant time: c3 T(n/2)
• 8.
  8 Methods for SolvingRecurrences • Iteration method • Substitution method • Recursion tree method • Master method
• 9.
  9 The recursion-tree method Convertthe recurrence into a tree: – Each node represents the cost incurred at various levels of recursion – Sum up the costs of all levels Used to “guess” a solution for the recurrence
• 10.
  10 Example 1 W(n) =2W(n/2) + n2 • Subproblem size at level i is: n/2i • Subproblem size hits 1 when 1 = n/2i ⇒ i = lgn • Cost of the problem at level i = (n/2i )2 No. of nodes at level i = 2i • Total cost: ⇒ W(n) = O(n2 ) 22 0 2 1lg 0 2lg 1lg 0 2 2)( 2 11 1 )( 2 1 2 1 )1(2 2 )( nnOnnOnnnW n nW i in i i n n i i =+ − =+      ≤+      =+= ∑∑∑ ∞ = − = − =
• 11.
  11 Example 2 E.g.: T(n)= 3T(n/4) + cn2 • Subproblem size at level i is: n/4i • Subproblem size hits 1 when 1 = n/4i ⇒ i = log4n • Cost of a node at level i = c(n/4i )2 • Number of nodes at level i = 3i ⇒ last level has 3log 4 n = nlog 4 3 nodes • Total cost: 2 ( ) ( ) ( ) )( 16 3 1 1 16 3 16 3 )( 23log23log2 0 3log2 1log 0 444 4 nOncnncnncnnT i iin i =Θ+ − =Θ+      ≤Θ+      = ∑∑ ∞ = − =
• 12.
  12 Example 2 -Substitution T(n) = 3T(n/4) + cn2 • Guess: T(n) = O(n2 ) – Induction goal: T(n) ≤ dn2 , for some d and n ≥ n0 – Induction hypothesis: T(n/4) ≤ d (n/4)2 • Proof of induction goal: T(n) = 3T(n/4) + cn2 ≤ 3d (n/4)2 + cn2 = (3/16) d n2 + cn2 ≤ d n2 if: d ≥ (16/13)c • Therefore: T(n) = O(n2 )
• 13.
  13 Example 3 (simplerproof) W(n) = W(n/3) + W(2n/3) + n • The longest path from the root to a leaf is: n → (2/3)n → (2/3)2 n → … → 1 • Subproblem size hits 1 when 1 = (2/3)i n ⇔ i=log3/2n • Cost of the problem at level i = n • Total cost: ⇒ W(n) = O(nlgn) 3/ 2 lg ( ) ... (log ) ( lg ) 3 lg 2 n W n n n n n n O n n< + + = = =
• 14.
  14 Example 3 W(n) =W(n/3) + W(2n/3) + n • The longest path from the root to a leaf is: n → (2/3)n → (2/3)2 n → … → 1 • Subproblem size hits 1 when 1 = (2/3)i n ⇔ i=log3/2n • Cost of the problem at level i = n • Total cost: ⇒ W(n) = O(nlgn) 3/ 2 3 / 2 (log ) 1 (log ) 0 ( ) ... 2 (1) n n i W n n n n W − = < + + = + <∑ 3/ 2 3/ 2 log log 2 3/ 2 0 lg 1 1 log ( ) ( ) lg ( ) lg3/ 2 lg3/ 2 n i n n n n n O n n O n n n O n = < + = + = + = +∑
• 15.
  15 Example 3 -Substitution W(n) = W(n/3) + W(2n/3) + O(n) • Guess: W(n) = O(nlgn) – Induction goal: W(n) ≤ dnlgn, for some d and n ≥ n0 – Induction hypothesis: W(k) ≤ d klgk for any K < n (n/3, 2n/3) • Proof of induction goal: Try it out as an exercise!! • T(n) = O(nlgn)