Time Complexity

Printable View

• 07-20-2010
Stuart Dickson
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 !!
• 07-20-2010
laserlight
What do you think it is? Is this binary tree balanced, and/or are you looking for both average case and worst case?
• 07-20-2010
RichSelian
Isn't it O(n) (n is the size of the tree)? This algorithm iterates each node by once.
• 07-20-2010
Stuart Dickson
I am looking for both average as well as worst case.
• 07-20-2010
phantomotap
^_^

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
• 07-20-2010
Stuart Dickson
I think it would be O(n log n) because every node will be visited atleast once.
• 07-20-2010
laserlight
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.)
• 07-20-2010
phantomotap
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