Understanding Big O notation - Cracking the coding interview example 9

Question

I got stuck with this two codes.

Code 1

int f(int n){
    if (n <= 1){
         return 1;
    }
    return f(n-1) + f(n-1);
}

Code 2 (Balanced binary search tree)

int sum(Node node){
    if(node == null){
        return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}

the author says the runtime of Code 1 is O(2^n) and space complexity is O(n)

And Code 2 is O(N)

I have no idea what's different between those two codes. it looks like both are the same binary trees

Answer 1

Well there's a mistake because the first snippet runs in O(2^n) not O(n^2).

The explanation is: In every step we decrement n but create twice the number of calls, so for n we'll call twice with f(n-1) and for each one of the calls of n-1 we'll call twice with f(n-2) - which is 4 calls, and if we'll go another level down we'll call 8 times with f(n-3): so the number of calls is: 2^1, then 2^2, then 2^3, 2^4, ..., 2^n.

The second snippet is doing one pass on a binary tree and reaches every node exactly once, so it's O(n).