Question

Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 2T(n/3) + n

Use the substitution method to verify your answer.

Answer 1

• The subproblem size for a node at depth ii is n / 3^in/3
  i
  .

  Thus, the tree has \lg n + 1lgn+1 levels and 2^{\lg n} = n^{\lg 2}2
  lgn
  =n
  lg2
  leaves.

  The total cost over all nodes at depth ii, for i = 0, 1, 2, \ldots, \lg n - 1i=0,1,2,…,lgn−1, is 2^i(n / 3^i) = (2 / 3)^i n2
  i
  (n/3
  i
  )=(2/3)
  i
  n.

  \begin{aligned} T(n) & = n + \frac{2}{3}n + \Big(\frac{2}{3}\Big)^3 n + \cdots + \Big(\frac{2}{3}\Big)^{\lg n - 1} n + \Theta(n^{\lg 2}) \\ & = \sum_{i = 0}^{\lg n - 1} \Big(\frac{2}{3}\Big)^i n + \Theta(n^{\lg 2}) \\ & = \frac{(2 / 3)^{\lg n} - 1}{(2 / 3) - 1}n + \Theta(n^{\lg 2}) \\ & = 3[(2 / 3)^{\lg n} - 1]n + \Theta(n^{\lg 2}) \\ & = 3[n^{\lg(2 / 3)} - 1]n + \Theta(n^{\lg 2}) \\ & = 3[n^{\lg 2 - \lg 3} - 1]n + \Theta(n^{\lg 2}) \\ & = 3[n^{\lg 2 - 1 + 1} - n] + \Theta(n^{\lg 2}) \\ & = O(n^{\lg 2}). \end{aligned}
  T(n)
  ​  
    
  =n+
  3
  2
  ​  
  n+(
  3
  2
  ​  
  )
  3
  n+⋯+(
  3
  2
  ​  
  )
  lgn−1
  n+Θ(n
  lg2
  )
  =
  i=0

  lgn−1
  ​  
  (
  3
  2
  ​  
  )
  i
  n+Θ(n
  lg2
  )
  =
  (2/3)−1
  (2/3)
  lgn
  −1
  ​  
  n+Θ(n
  lg2
  )
  =3[(2/3)
  lgn
  −1]n+Θ(n
  lg2
  )
  =2[n
  lg(2/3)
  −1]n+Θ(n
  lg2
  )
  =3[n
  lg2−lg3
  −1]n+Θ(n
  lg2
  )
  =3[n
  lg2−1+1
  −n]+Θ(n
  lg2
  )
  =O(n
  lg2
  ).
  ​  
  
  We guess T(n) \le cn^{\lg 2} - dnT(n)≤cn
  lg2
  −dn,

  \begin{aligned} T(n) & = 2T(\lfloor n / 3 \rfloor) + n \\ & \le 2 \cdot (c(n / 3)^{\lg 2} - d(n / 3)) + n \\ & = (2 / 3^{\lg 2})cn^{\lg 2} - (2d / 3)n + n \\ & = cn^{\lg 2} + (1 - 2d / 3)n, \end{aligned}
  T(n)
  ​  
    
  =2T(⌊n/3⌋)+n
  ≤2⋅(c(n/3)
  lg2
  −d(n/3))+n
  =(2/3
  lg2
  )cn
  lg2
  −(2d/3)n+n
  =cn
  lg2
  +(1−2d/3)n,
  ​  
  
  where the last step holds for d \ge 3d≥3.