There’s also a closed form for the Fibonacci numbers. It runs in O(1).

http://stsievert.com/blog/2015/01/31/the-mysterious-eigenval...