1
$\begingroup$

I started watching SICP lectures and am totally new to computer science. SICP. LEC 1B: Procedures and Processes; Substitution Model

I don't know why the time complexity of the Fibonacci sequence is O(Fib(n)). So, I googled about it,

he says

There's a thing that grows exactly at Fibonacci numbers. It's a horrible thing. You wouldn't want to do it. The reason why the time has to grow that way is because we're presuming in the model-- the substitution model that I gave you, which I'm not doing formally here, I sort of now spit it out in a simple way-- but presuming that everything is done sequentially. That every one of these nodes in this tree has to be examined. And so since the number of nodes in this tree grows exponentially because I add a proportion of the existing nodes to the nodes I already have to add one, then I know I've got an exponential explosion here.

Can anybody please explain what he's saying?

$\endgroup$
1
  • 2
    $\begingroup$ "time complexity of the Fibonacci sequence" -- by itself, a sequence doesn't have a time complexity. Do you mean the time complexity of computing the $n$-th element of the Fibonacci sequence is $O(Fib(n))$? Because even the straightforward method of repeatedly adding the last 2 terms together is exponentially faster than that, and using exponentiation by squaring to evaluate Binet's formula is exponentially faster than that. $\endgroup$ Feb 23, 2021 at 10:14

1 Answer 1

4
$\begingroup$

$\DeclareMathOperator{\fib}{fib}$If you choose to calculate $\fib(n)$ by using the naive recursion formula, then you need $\Theta (\fib(n))$ additions, and since the numbers involved grow to $c\cdot n$ bits for a not very large constant $c$, it will take $\Theta(n \cdot \fib(n))$ operations. (I may be wrong here because most of the numbers involved may be much smaller than $c \cdot n$ bits).

If you are reasonably clever and calculate $$\fib(0), \fib(1), \fib(2), \dots, \fib(n),$$ then you have $n$ additions of $c \cdot n$ bit numbers, which takes $\Theta(n^2))$ operations.

You can use matrix exponentiation to calculate $\fib(n)$ faster for large $n$, I'd estimate something like $M(n)$ where $M(n)$ is the time for an $n$-bit multiplication.

Most important is that for maybe $n = 100$ or $n = 200$, your computer has not a chance to calculate $\fib(n)$ using the naive recursive algorithm within your lifetime, while the simple method of calculating consecutive values will find the same result within microseconds on a newish smartphone.

$\endgroup$
4
  • $\begingroup$ There's even a closed form formula: $\left( \phi^n - (-\phi)^n \right) / \sqrt{5}$, where $\phi = (1 + \sqrt{5}) / 2$ is the golden ratio. $\endgroup$
    – Pål GD
    Feb 23, 2021 at 11:27
  • 2
    $\begingroup$ @PålGD As suggested by gnasher729, matrix exponentiation (which is really just a recurrence $(F_n,F_{n+1})\mapsto(F_{2n},F_{2n+1})$ if you don’t want to speak of matrices) is faster that computing $\phi^n$, as the latter needs to maintain working precision of $O(n)$ bits during the whole computation. That is, computing $F_n$ using matrix exponentiation takes $O(M(n))$ bit operations, whereas using $\phi^n$ it takes $O(M(n)\log n)$ operations. The algorithm using matrix exponentiation is also easier to implement, as it works purely with integers. $\endgroup$ Feb 23, 2021 at 12:15
  • 1
    $\begingroup$ @PålGD By the way, when you insert TeX definitions at the beginning of a post, do not leave any spaces between the definition and the subsequent text. Otherwise it produces spurious blank lines, as here. (I cannot correct it myself, as I do not have the reputation to edit.) $\endgroup$ Feb 23, 2021 at 12:17
  • 1
    $\begingroup$ @PålGD The correct formula is slightly different. You use (1 + sqrt(5)) / 2 and (1 - sqrt(5)) / 2. The second part raised to the n-th power goes towards 0 very quickly, do you can ignore it. And since you know the correct result is an integer, you just take phi(n) / sqrt(5) and round to the nearest integer. $\endgroup$
    – gnasher729
    Feb 23, 2021 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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