Reply To: Maths
@Crackerjack_404
You may have solved this by yourself already, but there is a decent covering of this in CLRS (Introduction to Algorithms) in the chapter on Number-theoretic algorithms. I can’t quite tell if you are asking about the derivation of the run-time or the relationship between the Fibonacci numbers and the golden ratio. If the former, then CLRS should give a good presentation. For the latter – I seem to recall you saying you know some linear algebra – try writing the recurrences which define the Fibonacci sequence as a matrix equation. Now try diagonalising the matrix. How does this help you?