Don't forget that there's also an O(1) closed form solution (and in fact you can derive a closed form solution for any linear recurrence relation: http://en.wikipedia.org/wiki/Recurrence_relation).

This is more useful though for things like calculating the size of a mortgage balance after N repayments.