I know that the Worst-case for $m$ search operations in a Splay-tree is $O(m\log n +n \log n)$

The thing I'm not sure of is how this runtime depends on the size of the subtrees of the searched nodes.

I tried reading the proof of this runtime to understand the relation between the size of the subtrees to the runtime but things don't add up so well.

Will be glad for any help.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.