Hello.
Can someone explain what is time complexity of this algorithm :
Thanks !!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); } }
What do you think it is? Is this binary tree balanced, and/or are you looking for both average case and worst case?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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
Last edited by phantomotap; 07-20-2010 at 02:58 AM. Reason: none of your business
I think it would be O(n log n) because every node will be visited atleast once.
Great, but my point is, what is your own answer? Aren't you going to venture something youself?
Agreed.
Well, the notation is rather broad in what it considers to be equivalent, I suppose.
EDIT:
Ah, this is better.
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.)
Last edited by laserlight; 07-20-2010 at 03:16 AM.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
*shrug*Well, the notation is rather broad in what it considers to be equivalent, I suppose.
I guess I could have added "in practice", but yeah the "limiting term" is still plain old "n".
Soma
