Fibonacci sequence: Difference between revisions

=== Recursive ===

Recursive version is slow, it is O(2ⁿ), or of exponential order.

[[File:Fōrmulæ - Fibonacci sequence 01.png]]

[[File:Fōrmulæ - Fibonacci sequence 02.png]]

[[File:Fōrmulæ - Fibonacci sequence result.png]]

It is because it makes a lot of recursive calls.

To illustrate this, the following is a functions that makes a tree or the recursive calls:

[[File:Fōrmulæ - Fibonacci sequence 03.png]]

[[File:Fōrmulæ - Fibonacci sequence 04.png]]

[[File:Fōrmulæ - Fibonacci sequence 05.png]]

=== Iterative (3 variables) ===

It is O(n), or of linear order.

[[File:Fōrmulæ - Fibonacci sequence 06.png]]

[[File:Fōrmulæ - Fibonacci sequence 07.png]]

[[File:Fōrmulæ - Fibonacci sequence result.png]]

=== Iterative (2 variables) ===

It is O(n), or of linear order.

[[File:Fōrmulæ - Fibonacci sequence 08.png]]

[[File:Fōrmulæ - Fibonacci sequence 09.png]]

[[File:Fōrmulæ - Fibonacci sequence result.png]]

=== Iterative, using a list ===

It is O(n), or of linear order.

[[File:Fōrmulæ - Fibonacci sequence 10.png]]

[[File:Fōrmulæ - Fibonacci sequence 11.png]]

[[File:Fōrmulæ - Fibonacci sequence result.png]]

=== Using matrix multiplication ===

[[File:Fōrmulæ - Fibonacci sequence 12.png]]

[[File:Fōrmulæ - Fibonacci sequence 13.png]]

[[File:Fōrmulæ - Fibonacci sequence result.png]]

=== Divide and conquer ===

It is an optimized version of the matrix multiplication algorithm, with an order of O(lg(n))

[[File:Fōrmulæ - Fibonacci sequence 14.png]]

[[File:Fōrmulæ - Fibonacci sequence 15.png]]

[[File:Fōrmulæ - Fibonacci sequence result.png]]

=== Closed-form ===

It has an order of O(lg(n))

[[File:Fōrmulæ - Fibonacci sequence 16.png]]

[[File:Fōrmulæ - Fibonacci sequence 17.png]]

[[File:Fōrmulæ - Fibonacci sequence result.png]]