On the time complexity of computing the $n$th Fibonnaci number
December 21, 2025We derive an interesting relationship between the number of additions required to compute the $n$th Fibonnaci number and the golden ratio $\varphi$.
“If you're thinking without writing, you only think you're thinking.” - Leslie Lamport
We derive an interesting relationship between the number of additions required to compute the $n$th Fibonnaci number and the golden ratio $\varphi$.
If you have spent time grinding LeetCode, you know that certain patterns emerge. While every problem is unique, the underlying data structures used to solve them often repeat.
We show how to express a discrete-time infinite impulse response (IIR) filter in state-space form.
We derive the Direct Form I and Direct Form II implementations of a discrete-time infinite impulse response (IIR) filter.
We prove that every square can be partitioned into $n$ squares for every $n \geq 6$.
We describe what fencepost errors are, how to avoid them, and provide a precise derivation for why they occur.