Time Complexity

Hello.

Can someone explain what is time complexity of this algorithm :

Code:

---

int maxDepth(struct node* node) {
  if (node==NULL) {
    return(0);
  }
  else {
    // compute the depth of each subtree
    int lDepth = maxDepth(node->left);
    int rDepth = maxDepth(node->right);
    // use the larger one
    if (lDepth > rDepth) return(lDepth+1);
    else return(rDepth+1);
  }
}

---

Thanks !!

What do you think it is? Is this binary tree balanced, and/or are you looking for both average case and worst case?

Isn't it O(n) (n is the size of the tree)? This algorithm iterates each node by once.

I am looking for both average as well as worst case.

^_^

Nice catch RichSelian! I missed that the first time I looked at it.

Well, actually, as the function is called for and operates on nodes that don't exist, I'd say that it is worse than "O(n)" even if it would be considered "O(n)".

Soma

I think it would be O(n log n) because every node will be visited atleast once.

Quote:

---

Originally Posted by Stuart Dickson

I am looking for both average as well as worst case.

---

Great, but my point is, what is your own answer? Aren't you going to venture something youself?

Quote:

---

Originally Posted by phantomotap

Nice catch RichSelian! I missed that the first time I looked at it.

---

Agreed.

Quote:

---

Originally Posted by phantomotap

Well, actually, as the function is called for and operates on nodes that don't exist, I'd say that it is worse than "O(n)" even if it would be considered "O(n)".

---

Well, the notation is rather broad in what it considers to be equivalent, I suppose.

EDIT:
Ah, this is better.

Quote:

---

Originally Posted by Stuart Dickson

I think it would be O(n log n) because every node will be visited atleast once.

---

You could check this hypothesis. Change the function such that it prints something for every node visited. (Oh wait, you're going to count anyway, so you might as well print a total count instead of printing for each node visited, since you will need to check this for some pretty large trees to see if the results correspond to your proposed complexity in the long run.)

Quote:

---

Well, the notation is rather broad in what it considers to be equivalent, I suppose.

---

*shrug*

I guess I could have added "in practice", but yeah the "limiting term" is still plain old "n".

Soma