IIT Kanpur

Question

There is a height-balanced tree T storing n elements. The greatest element smaller than x in T is called the predecessor of s in T. Given any positive number k, we wish to compute k predecessors of x in T. What is the time complexity of the best algorithm that can do this task?

A. O(k + log n)

B. O(k log n)

C. O(log(n + k))

D. O(n + k)

Comments

How?

---

@srestha ,please provide your solution.

---

1 predecessor find we can do in logn times

k predecessor we can find in klogn

rt?