# Fibonacci numbers

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