2
$\begingroup$

I am learning about time complexity now, and I am working with BST (Binary Search Trees).

This question needs some context and this is a follow up post to this post. Basically, I would like to compute the time complexity of the function below. The function below refers to a BinarySearchTree where 'u.l' represents the left child of 'u' and 'u.r' represents the right child of 'u'. Additionaly, 'u.p' represents the parent of 'u' and 'self.r' represents the root of our binary search tree.

def remove_node(self,u):                                
    if u.r == None or u.l == None: self.splice(u)       
    else:                                               
        w = u.r                                         
        while w.l != None:                              
            w = w.l
    u.x = w.x                                           
    self.splice(w)                                      

In the post I linked, we showed that splice(self,u) is a function with O(1) time-complexity and thus every statement that uses this function only will also have O(1) time complexity. Being aware of this, the best case scenario will be obviously when we enter the first if statement and in this case we will have that remove_node function is O(1) time-complexity (since u.x = w.x and self.splice(w) are also O(1) procedures).

With this being said, we must now study the worst case scenario, which is when we enter the else statement instead of the if statement. w = u.r is an atributtion and so it is O(1) in time complexity.

And now is where my trouble begins. The main question here is: How many times will be while cycle run? Well, this one is obvious. It will run as much times as the number of nodes in the left path of u.r to the end of the tree. But how would one translate this into time-complexity? Because we might have a BST such that u.r == None and thus the while cycle will run 0 times, but we might also have a BST such that u.r != None and in this case the while cycle will run a total of ntimes, where n represents the number of nodes to the left of u.r and its left descendants.

Below I give two examples of how many times the while cycle would run in this scenarios:

          u      
            \ 
             u.r
              /
           u.r.l                   => The while cycle will run 4 times
          /    \
     u.r.l.l   u.r.l.r
     /
u.r.l.l.l

But there are other examples. How would one determine the time complexity of this function? Thanks for any help in advance!

$\endgroup$

2 Answers 2

5
$\begingroup$

You could say that this function has a time complexity of $\mathcal{O}(h)$, where $h$ is the height of the BST.

You could be more precise and say that it is a $\Theta(h)$ in the worst case. This means that the complexity will never be more than linear in the height, but adds that this linear case can be reached (even if not every time as you have stated).

$\endgroup$
5
  • $\begingroup$ Shouldn't it be $\cal{O}(h)$, where $h$ is the height of the node $\texttt{u.r}$ we sent as an argument? Or am I making some confusion? $\endgroup$
    – Rodrigo
    Commented Apr 9, 2022 at 22:11
  • $\begingroup$ Sure, that's true, but in the worst case, the height of u.r is one less than the height of u, so it does not bring any interesting information. Do not try to be too specific when computing time complexity as long as you do not miss the worst case (and sometimes the average case). $\endgroup$
    – Nathaniel
    Commented Apr 9, 2022 at 22:16
  • $\begingroup$ That's right! Sorry, I guess my mathemathical instincts don't let me be not too specific ahhah $\endgroup$
    – Rodrigo
    Commented Apr 9, 2022 at 22:18
  • $\begingroup$ Sorry to bother again @Nathaniel , but I can't see how it is $\Theta(h)$ in the worst case (?). In my thinking, it should be $\Theta(a)$ in the worst case, where $a$ is the height of the node u.r.l where $h = a+2$ (in the worst case u would be the root of the tree) $\endgroup$
    – Rodrigo
    Commented Apr 10, 2022 at 11:18
  • 2
    $\begingroup$ The Landau's notations (theta or big oh) are asymptotic notations. As such, they don't care about additionnal constants. That means that in the worst case, where $h = a + 2$, then $\Theta(a) = \Theta(h)$. $\endgroup$
    – Nathaniel
    Commented Apr 10, 2022 at 12:28
4
$\begingroup$

While Nathaniel's answer is obviously right, there is something else to consider: Do the operations that you perform change the shape of your tree? I binary tree with 1000 nodes could have a height of 10, or it could be degenerated to a linked list with a height of 1,000. That would happen if you have a naive implementation of "add a node" and add 1,000 nodes in sorted order.

So what is the height of your average tree, based on the algorithms that you are using?

$\endgroup$
3
  • $\begingroup$ Thanks for your answer! How am I supossed to determine the height of my average tree? $\endgroup$
    – Rodrigo
    Commented Apr 9, 2022 at 22:58
  • $\begingroup$ Is the binary tree a balanced binary tree, perhaps an AVL tree or red-black tree? Otherwise, if it is an arbitrary tree, can you assume any input is equally likely, or will an attack attempt to induce the worst-case? $\endgroup$ Commented Apr 10, 2022 at 7:04
  • $\begingroup$ It is an arbitrary binary search tree, so I believe any input is equally likely, altought I feel like considering the worst-case is the best option $\endgroup$
    – Rodrigo
    Commented Apr 10, 2022 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.