Recursive function inside a simple loop time complexity

Question

Why is it that inside a for loop and calling a recursive function results to the time complexity of O(2^N) not O(N 2^N) of this code below. Basing on the book CTCI.

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

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

Because only the largest part is taken. The same reason iterating through an array twice gives ```O(n)``` complexity and not ```O(2n)``` complexity. The 2 is dropped. — Michael Bianconi, Aug 13 '19 at 17:43
@MichaelBianconi - then using your logic (exactly as stated) what about O(n Log n)? — PM 77-1, Aug 13 '19 at 17:50
Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Butiri Dan, Aug 13 '19 at 17:54
@MichaelBianconi that is not correct. In big O notation you drop all constants, but there is a difference in O(2^n) and O(n * 2^n). You may not ignore a nonconstant multiplier. — Maras, Aug 13 '19 at 18:01
@Maras You can ignore, because for large n, the `n` factor is almost irrelevant compared to the `2^n` — Mark Rotteveel, Aug 13 '19 at 18:12
@MarkRotteveel lol that's not because of large n, that's because 2^0+2^1+...+2^(n-1) is smaller than 2^n. the non-constant factor should never be ignored no matter how large or how small it is — mangusta, Aug 13 '19 at 18:55
@MarkRotteveel the `n` term dominates `log n` in `O(n logn)`. We do not drop the `log n` term and we shouldn't drop it here either — Mitch, Aug 13 '19 at 18:58

SomeDude · Answer 1 · 2019-08-14T11:40:01.023

Think of your recursive function as computing values in a tree.

        fib(n)
         /\
        /  \
 fib(n-1)   fib(n-2)

If you look carefully for n = 2, there are 3 values to be computed which is 2^(1+1) - 1 = 3 where 1 here is the height of the tree as in2^(h+1)-1

for n = 3, the height is h = 2

for n = 4, the height is h = 3

For all n, you need to add all of those: 2^2 - 1 + 2^3 - 1 + 2^4 - 1 + ....2^n - 1 -> is of the order of 2^(n+1)

Hence you get O(2^n)

Recursive function inside a simple loop time complexity

1 Answers1