Fibonacci: Iterative, recursion, memoization, Matrix exponentiation--NOT OPTIMAL OOP--Scared, ATH

#shorts
------------------
Imagine that you task is to compute the n-th term of the Fibonacci sequence, where n is BTW 0 and 10^18.

You can implement a iterative brute force solution. In this case, for huge ns, you'll wait a long time before you see a result, because its time complexity is O(n),

The recursive solution is worst. Not only because its O(2^n) time complexity, also because the call stack overflow,

You can fixed with memoization, to reduce the time complexity to O(n), but the space complexity will be O(n) o_O Really...

The best way is to use matrix exponentiation. Hey, hey, the time complexity is reduce to O(log n) and the space complexity is constant.

If you want a deep explanations of these all stuffs, just let me know in comments :)

[think_n_code]

< moo >

\ ^__^
\
(__)\ )\/\
||- - - -w |
|| ||

Imagine that you task is to compute the n-th term of the Fibonacci sequence, where n is BTW 0 and 10^18.

You can implement a iterative brute force solution. In this case, for huge ns, you'll wait a long time before you see a result, because its time complexity is O(n),

The recursive solution is worst. Not only because its O(2^n) time complexity, also because the call stack overflow,

You can fixed with memoization, to reduce the time complexity to O(n), but the space complexity will be O(n) o_O Really...

The best way is to use matrix exponentiation. Hey, hey, the time complexity is reduce to O(log n) and the space complexity is constant.

If you want a deep explanations of these all stuffs, just let me know in comments :)