I read the following link.
That compute $F_n$ in $O(\log n)$, but i can't find the space complexity of this matrix form of $F_n$.
2
-
$\begingroup$ 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?) $\endgroup$– greybeardNov 7, 2021 at 6:36
-
$\begingroup$ 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. $\endgroup$– D.W. ♦Nov 8, 2021 at 5:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
10
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.
answered Nov 7, 2021 at 12:47
-
-
2$\begingroup$ 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}$. $\endgroup$ Nov 7, 2021 at 14:32
-
$\begingroup$ Oh! Thank you, it's amazing... I spend so much times to find out why it's exponentially in $n$:) $\endgroup$– AhmadNov 7, 2021 at 14:37
-
$\begingroup$ So any methods such as DP, is exponentially in $n$ for computing $F_n$? $\endgroup$– AhmadNov 8, 2021 at 5:16
-
$\begingroup$ The length of $F_n$ in bits is only linear in $n$. $\endgroup$ Nov 8, 2021 at 5:37