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.

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);
}