打印所有斐波那契数从0到n的时间复杂度是多少?

这里也提出了同样的问题: Time complexity for all Fibonacci numbers from 0 to n ,但我无法理解提供的答案。

下面的代码从0到n打印所有斐波那契数,时间复杂度是多少?

void allFib(int n){
    for(int i = 0 ; i < n ; i++){
        System.out.println(i + ": " + fib(i));
    }
}    

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

我不明白为什么时间复杂度是O(2 ^ n)而不是O(n×2 ^ n)。据说:

fib(1)需要2^1步

...

fib(n)分2^n步

我看不出这是怎么回事,因为fib(1)基于else语句立即返回1,所以应该执行1步。即使这个陈述是真的,我仍然无法理解时间复杂度是如何O(2 ^ n)。