Fibonacci Sequence
The Fibonacci sequence has each term equal to the sum of the two before it (0,1,1,2,3,5,8...); it relates to the golden ratio and appears widely in nature and algorithms.
Purpose
To describe growth patterns, appearing in natural phenomena and algorithmic complexity analysis.
Mechanism
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Closed form (Binet's formula): F(n)=(φ^n-ψ^n)/√5, where φ=(1+√5)/2 is the golden ratio. Matrix exponentiation or fast doubling computes it in O(log n). Naive recursion is exponentially slow at O(φ^n).
Use cases
- Algorithm complexity analysis
- Technical indicator computation (Fibonacci retracement)
- Natural pattern modeling
- Dynamic programming teaching
Examples
- Input
F(10)Output550,1,1,2,3,5,8,13,21,34,55
Common errors
- Naive recursion recomputes subproblems and runs exponentially slow
- Use memoization or fast matrix exponentiation
Related terms
Factorial
The factorial n! = n×(n-1)×...×1 is the basis of permutations and combinations; it grows extremely fast, with 20! already exceeding the 64-bit integer range. GLOSSARY
Big O Notation
Big O notation describes the asymptotic upper bound of a function, used to analyze algorithm time/space complexity while ignoring constants and lower-order terms. GLOSSARY
BigInteger
BigInteger is an arbitrary-precision integer type, not limited by a fixed word size, used for computations beyond the native integer range (such as cryptography and combinatorics). GLOSSARY