Having trouble computing time complexity of a given function in Python

Question

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!

Answer 1

I agree that the best case time estimate would be O(1).
Very often determining the worst case time complexity is more difficult then best case, simply because it assumes a more complex situation. That is also the case here.

If we are specifically thinking of a worst case, we can think of what input would make the while loop run the longest, considering the input binary tree.
All in all, the while loop will have at worst, as many iterations as the maximum depth of the tree. That is also what you see in the example supplied in your question.
We can also further reason about this maximum depth in terms of it's relation to the amount of total nodes (further referred to as n). For instance, if the tree is not being kept in balance, then in the very worst case, all nodes are stacked to one side and the amount of nodes is close to or equal to n.
If it is being kept in balance, the maximum depth scales with log2(n).

In generell, if you don't know, can't tell or have no control over the balance in the tree it would also be valid to specify the worst case time complexity as something like:

O(d) where d is the maximum depth of the tree