Fibonacci sequence: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Aerobar (talk | contribs)
1,151 edits
m →‎{{header|TI-57}}: correct index
Laurence (talk | contribs)
2,121 edits
Line 6,844:
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Fibonacci_numbers}}
 
=== Recursive ===
 
Recursive version is slow, it is O(2<sup>n</sup>), 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]]
 
=={{header|GAP}}==
Retrieved from "https://rosettacode.org/wiki/Fibonacci_sequence"