Understanding Big O notation - Cracking the coding interview example 9

user_4884241 0
Viewed 1480

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

tree notation big-o algorithm
7 Answers

You’re confused between the “N” of the two cases. In the first case, the N refers to the input given. So for instance, if N=4, then the number of the functions being called is 2^4=16. You can draw the recursive map to illustrate. Hence O(2^N).

In the second case, the N refers to the number of nodes in the binary tree. So this N has no relation with the input but the amount of nodes that already exists in the binary tree. So when user calls the function, it visits every node exactly once. Hence O(N).

user_118156870

For Code 2, to determine the Big O of a function, didn't we have to consider the cost of the recurrence and also how many times the recurrence was run?

If we use two approach to estimate the Big O using recursive tree and master theorem:

Recursive tree: total cost in each level will be cn for each level as the number of recursive call and the fraction of input are equal, and the level of tree is lg(n) since it's a balanced binary search tree. So the run time should be nlg(n)?

Master Theorem: This should be a case 2 since f(n) = n^logbase a (b). So according to the master theorem, it should be nlg(n) running time?

user_96929660

We can think of it as O(2^Depth).

In the first example: The depth is N, which happens to be the input of the problem mentioned in the book.

In the second example: It is a balanced binary search tree, hence, it has Log(N) levels (depth). Note: N is the number of elements in the tree.

=> Let's apply our O(2^Depth).. O(2^(Log(N)) = O(N) leaving us with O(N) complexity.

Reminder:

  • In computer science we usually refer to Log2(n) as Log(n).
  • The logarithm of x in base b is the exponent you put on b to get x as a result.

In the above complexity: O(2^(Log(N), we're raising the base 2 to Log2(N) which gives us N. (Check the two reminders)

This link can be useful.

user_45022120
Related