Fibonacci numbers

Answer

Learn more...

This are some approaches calculating nth number of Fibonacci sequence

First things first, lets 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 to get the answer

There are some other approaches, but these are my favorite

Some links to explore more