Constant-time Fibonacci
This is the second part in a 2-part series on the “Fibonacci” interview problem. We are building off of a previous post, so take a look at Part I if you haven’t seen it.
Previously, we examined the problem and constructed a logarithmic-time solution based on computing the power of a matrix. Now we will derive a constant time solution using some more linear algebra. If you had trouble with the linear algebra in part I, it may help to read up on matrices, matrix multiplicaiton, and special matrix operations (specifically determinants and inverses) before moving on.
Eigenvalues and eigenvectors are a bit of a magical concept in linear algebra. The definition of eigenvalues is: “A matrix times an eigenvector equals an eigenvalue times an eigenvector.” As an equation, the eigenvalues ($\lambda$) and eigenvectors ($\textbf{v}$) of a matrix ($\textbf{A}$) can be computed by solving:
In more intuitive terms, each matrix has a set of vectors (its eigenvectors) which are scaled by a constant factor (the eigenvalues) when multiplied by the matrix. If we think of matrix multiplication as a transformation of a shape in space, the eigenvectors are the directions along which the matrix stretches the shape, and the eigenvalues are the scaling factors.
