Recursion tree m=3.n=4 subproblem mtn 2,2 Height=m+n= work potentially exponential but were solving subproblems already solved c 2001 by Charles E Leiserson Introduction to Agorithms Day 26 L15.9© 2001 by Charles E. Leiserson Introduction to Algorithms Day 26 L15.9 same subproblem , but we’re solving subproblems already solved! Recursion tree m = 3, n = 4: 3,43,4 2,42,4 1,41,4 3,33,3 2,32,3 3,23,2 1,31,3 2,22,2 Height = m + n ⇒ work potentially exponential. 2,32,3 1,31,3 2,22,2 m+n