C++

Forum

 
Big O of recursive functions.

trevormoon (45)
Hey guys I have several functions that I'm not sure if I got the big O for them correct.

Ok for the first function I think its O(logn)^2.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
template <class T>
void Binary_tree<T>::recursive_preorder(Binary_node<T> *sub_root,
                                            void (*visit)(T &))
{
  if(sub_root != NULL)
    {
        (*visit)(sub_root->data);
       recursive_preorder(sub_root->left,visit);
       recursive_preorder(sub_root->right,visit);
    }
        
}


For the second function I think it would also be O(logn)^2 since it calls recurssive_preorder.

1
2
3
4
5
6
7
 
template <class T>
void Binary_tree<T>::preorder(void (*visit)(T &))

{
  recursive_preorder(root,visit);
}


Would this function also be O(logn)^2?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template <class T>
int Binary_tree<T>::recursive_height(Binary_node<T> *sub_root) const

{
   if(sub_root == NULL)
      return 0;
   else {
         int hleft = recursive_height(sub_root->left);
         int hright = recursive_height(sub_root->right);
         if(hleft>=hright)
            return 1 + hleft;
         else return 1+ hright;
   }
}


Finally would this function be O (logn)^2 as well?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
  template <class T>
Binary_node<T>* Binary_tree<T>::recursive_copy(Binary_node<T>* sub_root)

{
  if(sub_root ==NULL)
      return NULL;
     else{
          Binary_node<T>* copy_sub_root = new Binary_node<T>(sub_root->data);
          copy_sub_root->left = recursive_copy(sub_root->left);
          copy_sub_root->right = recursive_copy(sub_root->right);
          return copy_sub_root;
         }
}
Last edited on
trevormoon (45)
After looking at them a little closer I think big O would actually be O(n) is that correct?
helios (17575)
They're actually all linearithmic. Besides the time to perform the useful task (calling the function, copying, etc.), you also have to consider the time required to move up and down the tree. Moving from one element to the next doesn't take constant time like with an array or a list.
Topic archived. No new replies allowed.