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 '14 at 8:50
• Ya i just went through that. implementing using matrix right? Is that liner ? 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). 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. 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) Feb 2 '14 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 '14 at 8:52
• And that is why one should use memoization when programming a Fibonacci sequence. 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. 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);
}