Time Complexity

This is a discussion on Time Complexity within the C Programming forums, part of the General Programming Boards category; Hello. Can someone explain what is time complexity of this algorithm : Code: int maxDepth(struct node* node) { if (node==NULL) ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    16

    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 !!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    What do you think it is? Is this binary tree balanced, and/or are you looking for both average case and worst case?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    Isn't it O(n) (n is the size of the tree)? This algorithm iterates each node by once.

  4. #4
    Registered User
    Join Date
    Apr 2010
    Posts
    16
    I am looking for both average as well as worst case.

  5. #5
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,281
    ^_^

    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

  6. #6
    Registered User
    Join Date
    Apr 2010
    Posts
    16
    I think it would be O(n log n) because every node will be visited atleast once.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    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.)
    Last edited by laserlight; 07-20-2010 at 03:16 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,281
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. NtSetSystemTime() failed
    By medp7060 in forum C++ Programming
    Replies: 11
    Last Post: 04-02-2010, 02:58 AM
  2. Representing floats with color?
    By DrSnuggles in forum C++ Programming
    Replies: 113
    Last Post: 12-30-2008, 08:11 AM
  3. measure time complexity
    By l2u in forum C++ Programming
    Replies: 1
    Last Post: 11-14-2008, 07:07 AM
  4. Is this really true or it's just science fiction?
    By Nutshell in forum A Brief History of Cprogramming.com
    Replies: 145
    Last Post: 04-09-2002, 06:17 PM
  5. time class
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 09:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21