The Substitution Method

Idea: Make an intelligent guess and prove by induction.

Example:

• Solve: $T(n) = 2 T(\lfloor n/2 \rfloor) + n$
• Guess: $T(n) \le c n \log n$.
• Prove:
  • Base case: Assume constant size inputs take constant time.
  • Assume: $T(\lfloor n/2 \rfloor) \le c \lfloor n/2 \rfloor \log(\lfloor n/2 \rfloor)$
  • Then:
  • So we see we need $c \ge 1$.