SG
← Back

Solving Linear Recurrence Relations

Closed forms via characteristic equations for T(n)=aT(n-1)+b.

complexityrecurrenceUpdated 2025-09-01

Example

  • T(n)=T(n-1)+c → T(n)=T(0)+nc

Homogeneous

  • Solve roots of r^k - ... =0