O(h+k) bound in Problem 15.3

#1

Can someone explain what “number of times it descends in the tree is at most h more than number of times it ascends” and how O(h+k) is coming to be?

0 Likes

#2

Hi @googlejob,

h comes from the fact finding the smallest element (which locates at the leftmost child), which might be O(h) deep. k comes from the fact you need find k smallest elements.

0 Likes