Hi,
I think that the complexity given for the query of most visited K pages is erroneous.
As the predecessor call on the height balanced BST takes O(log m) (m distinct pages seen so far), and calling that k-1 times, the complexity is O(k * log m), not O(k+log m), as stated on page 269.
Please correct me if I made a mistake.
Hi,
it cannot be k*O(log m). Intuitively, when we query k pages, we don’t traverse our tree top to bottom each time. Most of the time our path is smaller.
Let’s say we want to query all visited pages, so k = m.
You are saying that complexity would be m*O(log m).
So we go from min node to max node. Each node will be visited at most 3 times, so complexity is linear to the number of nodes, which is O(m), which is the same as O(k) in out case.
We need “+ log m” part, because if the k = 1 we might traverse the tree from bottom to top which is O(log m).
So the complexity is O(max(k, log m)) == O(k + log m).
Here is the link: http://stackoverflow.com/questions/18789456/k-successive-calls-to-tree-successor-in-bst
@damluar is correct, as each predecessor call might not be O(1) but amortized that will be O(1) for each call. Eventually that will be O(k + log(m)) time.