Taking out the Complexity of the following

How can we take out the complexity of the update function(without lazy propagation) in a segment tree.

alt text

Now the drawing is not good but i just want to clear my concepts. What would be the O(?) for updating [1,15] (without lazy propagation),Plase help .

Number of leaf nodes = N = 8

Number of nodes on path to each leaf node = log(N)

Complexity to update each node on path to leaf node = log(N)

Complexity to update all nodes = N*log(N)

1 Like