# Space complexity Matrix form of Fibonacci numbers

That compute $$F_n$$ in $$O(\log n)$$, but i can't find the space complexity of this matrix form of $$F_n$$.

• Welcome to COMPUTER SCIENCE @SE. How big is $F_n$ (the output)? (and what is the relation to • your question • the time complexity you see claimed?) Nov 7, 2021 at 6:36
• Please edit your question to make it self-contained, so we don't have to click on an external link to understand your question and we can still understand what is being asked even if the link stops working.
– D.W.
Nov 8, 2021 at 5:19

The algorithm uses a constant number of $$2 \times 2$$ matrices which contain Fibonacci numbers $$F_m$$ for $$m \leq n$$, as well as a few indices ranging up to $$n$$.

This should be enough information to compute the space complexity of the algorithm, whether expressed in machine words or in bits.

As an aside, since $$F_n$$ grows exponentially in $$n$$, it is misleading to count only the number of arithmetic operations, rather than the bit complexity of the computation.

• Why $F_n$ grows exponentially in $n$? Nov 7, 2021 at 14:30
• This follows from the closed-form expression $F_n = \bigl((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n\bigr)/\sqrt{5}$. Nov 7, 2021 at 14:32
• Oh! Thank you, it's amazing... I spend so much times to find out why it's exponentially in $n$:) Nov 7, 2021 at 14:37
• So any methods such as DP, is exponentially in $n$ for computing $F_n$? Nov 8, 2021 at 5:16
• The length of $F_n$ in bits is only linear in $n$. Nov 8, 2021 at 5:37