# 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)`.

• 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. Feb 2, 2014 at 8:50
• Ya i just went through that. implementing using matrix right? Is that liner ? Feb 2, 2014 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). Feb 2, 2014 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. Feb 2, 2014 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)` Feb 2, 2014 at 20:08

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. Feb 2, 2014 at 8:52
• And that is why one should use memoization when programming a Fibonacci sequence. Feb 2, 2014 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. Feb 2, 2014 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);
}
``````