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
– Michael Bianconi, Commented Aug 13, 2019 at 17:43
@MichaelBianconi - then using your logic (exactly as stated) what about O(n Log n)? — PM 77-1
– PM 77-1, Commented Aug 13, 2019 at 17:50
@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
– Maras, Commented Aug 13, 2019 at 18:01
@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
– mangusta, Commented Aug 13, 2019 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
– Mitch, Commented Aug 13, 2019 at 18:58

SomeDude · Accepted Answer · 2019-08-14 11:40:01Z

2

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)

edited Aug 14, 2019 at 11:40

answered Aug 13, 2019 at 18:00

SomeDude

14.3k5 gold badges26 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursive function inside a simple loop time complexity

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related