Good Algorithms beat Supercomputers

Thinking about software, life, the universe and everything.

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

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s