Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
    
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 at 8:50
    
Ya i just went through that. implementing using matrix right? Is that liner ? –  user3261177 Feb 2 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 at 9:26
1  
@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. –  Raphael M. Feb 2 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 at 20:08

4 Answers 4

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.

share|improve this answer
    
Ya thanks a lot. i was actually concentrating on seq, thinking seq=complexty. i was wrong. –  user3261177 Feb 2 at 8:52
2  
@user3261177 you should accept the answer that you consider helpful. –  Silviu Burcea Feb 2 at 11:54
    
And that is why one should use memoization when programming a Fibonacci sequence. –  syb0rg Feb 2 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 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)
share|improve this answer

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.

share|improve this answer
    
Thanks :) was confused with seq –  user3261177 Feb 2 at 8:52

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);
}
share|improve this answer
    
Yup, Thanks for the info –  user3261177 Feb 2 at 9:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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