It is good to remember why well designed algorithms matter. I decided to experiment with the well known Fibonacci number. I have this sticky note plastered on my monitor at work.
“Good Algorithms beat Supercomputers”. Lets take a glimpse into why that is the case.
The fibonacci recurrence is defined as:
F(N) = F(N-1) + F(N-2), N>1
and F(N) = N for N: 0 or 1
This will lead to a series of numbers in order 0,1,1,2,3,5,8,….
Translating this to code we have the naive algorithm as:
However this naive algorithm suffers from a fatal flaw. As the values of n get larger, we end up computing fibonacci values repeatedly for multiple m<n. This is computationally expensive as n becomes larger.
eg. Fib(5) = Fib(4) + Fib(3)
Fib(4) = Fib(3) + Fib(2)
Fib(3) = Fib(2) + Fib(1)
Fib(2) = Fib(1) + Fib(0)
We can already see Fib(2) being computed…
View original post 230 more words