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
With this being said, we must now study the worst case scenario, which is when we enter the
else statement instead of the
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
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!