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