# difference between exponential and logarithmic growth

Why
`for(k=1;k<=n;k*=2)` grows logarathmically = `O(logn)` but I feel it grows exponentially, as the seq look like `1,2,4,8....`

and for fibonacci series people say it grows exponentially. which for me doesnt look like `0,1,1,2,3,5...` but for tis they tell `O(2^n)`.

PLease explain

• As pointed out by Idan Arye, computing the Fibonacci series is only exponential with a naive recursive implementation. Other implementations (including recursive ones) are linear. – Giorgio Feb 2 '14 at 8:50
• Ya i just went through that. implementing using matrix right? Is that liner ? – user3261177 Feb 2 '14 at 8:55
• In fact neither the naive iterative implementation nor the matrix implementation are O(n). The nth Fibonacci number has O(n) digits, the best known algorithms are O(n log n). – U2EF1 Feb 2 '14 at 9:26
• @U2EF1 I think you're mistaking the fibonacci sequnce with something else, since the iterative version usually IS O(n) and Giorgio got an O(n) recursive implementation in his answer too. – user1942027 Feb 2 '14 at 12:23
• @tribse The iterative version is not O(n) on real computers, since we do not have O(1) arithmetic for arbitrary precision integers. Otherwise the algorithm would be O(1)! `F(n) = floor(phi^n / sqrt(5) + 1/2)` – U2EF1 Feb 2 '14 at 20:08

## 4 Answers

You're misunderstanding the meaning. They are probably talking about the complexity of an algorithm, which got nothing to do with the resulting sequence of numbers (which you seem to talk about).

Just look at some snippets.

Compare for example `for(k=1;k<=5000;k*=2)` with `for(k=1;k<=10000;k*=2)`. You'll see that the second will only take 1 more iteration. In fact doubling `n` will always take only one step more.

Now lets look at the algorithm for the fibonacci sequence that was probably being talked about:

``````int fibonacci(int n)  {
if(n <= 1) return n;
else return fibonacci(n - 1) + fibonacci(n - 2);
}
``````

Now lets look at how often the function gets executed for several values for `n`:

``````n = 0:  1    function call
n = 1:  1   function call
n = 2:  3   function calls
n = 3:  5   function calls
n = 4:  9   function calls
n = 5:  15  function calls
n = 6:  25  function calls
n = 7:  41  function calls
n = 8:  67  function calls
n = 9:  109 function calls
n = 10: 177 function calls
``````

In fact you got the one function call you make when calling `fibonacci(n)` + the amount of function calls being made in `fibonacci(n-1)` + the amount of function calls in `fibonacci(n-2)`.
Therefore increasing `n` just slightly would make an huge increase in the number of function calls actually being made.

• Ya thanks a lot. i was actually concentrating on seq, thinking seq=complexty. i was wrong. – user3261177 Feb 2 '14 at 8:52
• And that is why one should use memoization when programming a Fibonacci sequence. – syb0rg Feb 2 '14 at 16:00
• "They are probably talking about the complexity of an algorithm, which got nothing to do with the resulting sequence of numbers ". It depends on what you are counting. In the above case only the number of operations count, but if the index was used during other computations then its size might matter in the asymptotic complexity of the algorithm. This is a common misconception that make people think we can compute fibonacci numbers in `O(logn)` time using the matrix trick, when, since they grow as `2^n` they also require `n` bits of output which cannot be generated by an O(logn) algorithm. – Bakuriu Feb 2 '14 at 19:00

For the first snippet, you are correct, the sequence is 1, 2, 4, 8, but you miss the point. Make a table, n and the number of steps to take. Sample:

n / sequence length

``````1 / 1
2 / 2
4 / 3
8 / 4
16 / 5
``````

As you can see, you get O(log n).

For Fibonacci, you have f(n) = f(n-1) + f(n-2). For every n step, you calculate 2 more steps. For every n-1 steps you also have to calculate 2 steps. You stop at n = 1 or n = 2, the last one with 2 more steps being n = 3. For `nth` step, you have, more or less:

``````2^3 + 2^4 + .. + 2^(n-1) = 2^n - 2^0 - 2^1 - 2^2 = O(2^n)
``````

The asymptotic growth is not about how the numbers in the sequence grow - it's about how long it takes to calculate the sequence for a given `n`.

In `for(k=1;k<=n;k*=2)`'s case, it only takes a single extra iteration to calculate for `n*2` compared to `n`, so assuming the iteration's execution time is `O(1)`, the growth is logarithmic.

In Fibonacci's case, if you use the naive recursive algorithm, it takes twice as long to calculate for `n+1` compared to `n`, so the growth is exponential.

Just an observation regarding the complexity of calculating the Fibonacci numbers. As others have pointed out, the naive implementation

``````int fibonacci(int n)
{
if (n <= 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
``````

is exponential. On the other hand, the following implementation is linear:

``````int fibonacci_helper(int f0, int f1, int p, int n)
{
if (p == n)
return f0 + f1;
else
return fibonacci_helper(f1, f0 + f1, p + 1, n);
}

int fibonacci(int n)
{
if (n <= 1)
return n;
else
return fibonacci_helper(0, 1, 2, n);
}
``````