Fibonacci numbers


Learn more...

These are some approaches calculating nth number of Fibonacci sequence

First things first, let's define Fibonacci sequence. First and second elements will be 1 and 1

Let n-th Fibonacci number be the sum of two previous numbers of the same sequence

So we get: 1, 1, 2, 3, 5, 8, 13 etc.

First approach `O(n)` (using the definition)

We can just store 2 values: current and previous elements

Updating `v_1` and `v_2` such way: `tmp = v_1`, `v_1 = v_1 + v_2`, `v_2 = tmp` for `n - 2` times, in `v_2` we'll get the answer

Second approach `O(log_2n)` (math)

We can use the fact that `(1, 1) * ((0, 1), (1, 1))^n` = `(F_n, F_(n+1))`

Simply multiplying matrices that way or using the binary power algorithm will help us get the answer

There are some other approaches, but listed above are my favorite

Links to explore further