FIB

RU: FIB

A Fibonacci number is a member of the sequence defined by F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2): 0, 1, 1, 2, 3, 5, 8, 13, … Computing F(n) naively by double recursion runs in O(2ⁿ) time; memoised recursion or iteration reduces this to O(n); matrix exponentiation achieves O(log n).