I’ve been studying algorithms lately. I’m still in the early stages
of this trek, but I have concluded that coming up with the right
solution is not that important. It’s far more valuable to be able to attack a
problem with multiple strategies (*note: code examples are written in JavaScript*).

As an example, take the Fibonacci series
where the n^{th} Fibonacci number is defined by the recurrence relation
`F(n) = F(n - 1) + F(n - 2)`

, and the definitions `F(0) = 1`

and `F(1) = 1`

.
It’s a recurrence relation, and as far as algorithms go, I find it the most
naturally recursive problem.

To write a function that is able to generate the n^{th} Fibonacci number
`F(n)`

, a recursive function is sufficient:

```
function fibonacci(n) {
if (n < 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
```

It’s evident that this function satisfies the recurrence relation and the
definitions: calling `fibonacci(0)`

or `fibonacci(1)`

will return `1`

(since
one and zero are less than 2); and for numbers two and above, the result is the
sum of the previous two Fibonacci numbers.

Although mathematically correct, this solution is computationally inefficient.
You can read some of the literature to discover that the runtime complexity is
*O(2 ^{n})* (really

*1.6*.

^{n})In an effort to be able to calculate larger Fibonacci numbers, we
recognize that `fibonacci(3 - 1)`

returns the same value as `fibonacci(4 - 2)`

and we can avoid computing the same Fibonacci number by storing previously
calculated values. This technique is called memoization:

```
// Initialize our map object with the seed values
var previous = {
0: 1,
1: 1
};
function fibonacci(n) {
// This value was previously calculated
if (n in previous) {
return previous[n];
}
// First time calculating this result, we'll add it to our collection
previous[n] = fibonacci(n - 1) + fibonacci(n - 2);
return previous[n];
}
```

This way a Fibonacci number is calculated only once - our runtime complexity is
`O(n)`

. We now have to store all previously calculated values so our storage
complexity is also `O(n)`

(we store every result up to `F(n)`

), which is not
a problem for small enough values of `n`

.

There is one approach where we can still calculate in linear time without
keeping every previous Fibonacci number in memory. This approach requires
careful analysis to realize that a non-recursive approach is possible by
retaining `F(n-1)`

and `F(n - 2)`

in variables:

```
function fibonacci(n) {
var res1 = 1;
var res2 = 1;
if (n < 2) {
return 1;
}
var tmp = null;
while (n > 2) {
tmp = res1;
// F(n - 1) becomes the sum of the two previous Fibonacci numbers
res1 = res1 + res2;
// Previous F(n - 1) becomes F(n - 2)
res2 = tmp;
// Decrease n
n -= 1;
}
return res1 + res2;
}
```

This gives us an `O(n)`

runtime complexity and our storage does not need to
grow regardless of how large `n`

is.

There are many problems where a variety of solutions will satisfy the problem exactly, and one approach is likely to be much better than others. The unoptimized solution is typically straightforward enough to write the first time encountering the problem, but the others require more exposure and familiarity with similar problems to approach in more creative ways. I will continue to write about such problems in the next blog post.