3 ms·
A fun quote from the article, discussing a basic Fibonacci recursive implementation: > Each call branches into two more calls, so the total number of calls gro
by ventana 3mo ago
A fun quote from the article, discussing a basic Fibonacci recursive implementation:
> Each call branches into two more calls, so the total number of calls grows as O(2ⁿ).
Well, no, not really. If anyone bothers counting how many recursive calls are actually made, the result is far from powers of two:
n | result | # of calls
1 | 1 | 1
2 | 1 | 3
3 | 2 | 5
4 | 3 | 9
5 | 5 | 15
6 | 8 | 25
7 | 13 | 41
8 | 21 | 67
9 | 34 | 109
10 | 55 | 177
11 | 89 | 287
12 | 144 | 465
13 | 233 | 753
14 | 377 | 1219
15 | 610 | 1973
16 | 987 | 3193
17 | 1597 | 5167
18 | 2584 | 8361
19 | 4181 | 13529
20 | 6765 | 21891
A curious person will then calculate the actual ratio:
n | result | # of calls | ratio
1 | 1 | 1 | 1
2 | 1 | 3 | 3
3 | 2 | 5 | 1.6666666666666667
4 | 3 | 9 | 1.8
5 | 5 | 15 | 1.6666666666666667
6 | 8 | 25 | 1.6666666666666667
7 | 13 | 41 | 1.64
8 | 21 | 67 | 1.6341463414634145
9 | 34 | 109 | 1.626865671641791
10 | 55 | 177 | 1.6238532110091743
11 | 89 | 287 | 1.6214689265536724
12 | 144 | 465 | 1.6202090592334495
13 | 233 | 753 | 1.6193548387096774
14 | 377 | 1219 | 1.6188579017264275
15 | 610 | 1973 | 1.6185397867104183
16 | 987 | 3193 | 1.6183476938672072
17 | 1597 | 5167 | 1.6182273723770748
18 | 2584 | 8361 | 1.6181536675053223
19 | 4181 | 13529 | 1.6181078818323167
20 | 6765 | 21891 | 1.6180796806859339
and will notice that it gets close to φ = (1 + √5) / 2 ≈ 1.618033989, which makes the number of recursive calls O(φⁿ), which is much more fun than O(2ⁿ).
- Chinjut 3mo agoYes, because the number of calls in this setup is 2 * the next result - 1, and the Fibonacci sequence itself grows at this Θ(φⁿ) rate.
- veltas 3mo agoReally it's worse than exponential, because the size of the input is not n, it's the number of bits needed to store n i.e. log n. So as the number of bits k grow, it's growing phi^(2^k).
- recursive 3mo agoBig O analysis never implies size in bits. It's just often done. In this case, n is just the numerical value of the input, so I don't think this is correct.
- veltas 3mo agoIf you want to measure growth based on another variable you are allowed to do so, but for most algorithms I'm more interested in the growth of time according to input size.
- recursive 3mo agoThen we may conclude that you may not be interested in this.
- veltas 3mo agoWhat do you mean by this? I was interested in article and parent, that's why I responded.
- recursive 3mo agoYou said "really it's worse than exponential". But that's based on your own personally-interesting way of measuring n, which is inconsistent with the given way.
- veltas 2mo agoHere is the conventional use of Big O notation where the input is a number: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Complexity https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality... As you'll see they are using the number of digits, not the value of the number, because the number of digits is the size of the input. You can find countless examples of this in literature. So this is not a 'personally-interesting' way as you assert.