Complexity of the following recursive code

Question

Trying to figure out why complexity is O(n) for this code:

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

Node is:

class Node {
  int value;
  Node left;
  Node right;
}

This is from CCI book. Shouldn't it be O(2^n) since it iterates through each node?

Yet this one is O(2^n), which is clear to me why:

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

Thanks for help.

It visits each node exactly once, so O(n) seems right. – 500 - Internal Server Error Oct 22 '16 at 01:32 — 500 - Internal Server Error, Oct 22 '16 at 01:32
@500-InternalServerError ok I think I get this now. Thanks – Anton Kim Oct 22 '16 at 01:41 — Anton Kim, Oct 22 '16 at 01:41

score 0 · Accepted Answer · edited May 23 '17 at 12:16

An algorithm is said to take linear time, or O(n) time, if its time complexity is O(n). Informally, this means that for large enough input sizes the running time increases linearly with the size of the input. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list.

From Wikipedia

It is very reasonable that the alogrithm complexity is O(n) since the recursive function numbers of calls is proportional to the number of items in the tree, there is n items in the tree and we will pass each item only once, this sounds very linear realtion to me.

In contrast to the other algorithm which is very similar to recursive Fibonacci Sequence algorithm, it this algorithm we will pass each number from 1 until n much more times than once and not linear proportional to n either, this explains why it has O(2^n) complexity.

Complexity of the following recursive code

1 Answers1