Is it true that splay trees have O(logn) amortized complexity ?

Category: QuestionsIs it true that splay trees have O(logn) amortized complexity ?
Editor">Editor Staff asked 1 month ago

Is it true that splay trees have O(logn) amortized complexity ?
 
(a) true
 
(b) false
 
Enquiry is from Splay Tree topic in section Binary Trees of Data Structures & Algorithms I
 
I had been asked this question by my school teacher while I was bunking the class.

1 Answers
Editor">Editor Staff answered 1 month ago

The correct choice is (a) true
 
Best explanation: We go with amortized time complexity when we feel that not all operations are worst and some can be efficiently done. in splay trees not all splay operations will lead to O(logn) worst case complexity.