1
$\begingroup$

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$.

$\endgroup$
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$
    – greybeard
    Nov 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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Why $F_n$ grows exponentially in $n$? $\endgroup$
    – Ahmad
    Nov 7, 2021 at 14:30
  • 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$
    – Ahmad
    Nov 7, 2021 at 14:37
  • $\begingroup$ So any methods such as DP, is exponentially in $n$ for computing $F_n$? $\endgroup$
    – Ahmad
    Nov 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.