What is the time complexity of for achieving competitive ratio by tango tree?

Category: QuestionsWhat is the time complexity of for achieving competitive ratio by tango tree?
Editor">Editor Staff asked 1 month ago

What is the time complexity of for achieving competitive ratio by tango tree?
 
(a) O (log n)
 
(b) O (n^2)
 
(c) O (n!)
 
(d) O (log (log n))
 
My question is based upon Binary Trees topic in section Binary Trees of Data Structures & Algorithms I
 
I had been asked this question in an internship interview.

1 Answers
Editor">Editor Staff answered 1 month ago

The correct choice is (d) O (log (log n))
 
The explanation is: Tango tree is an online binary search tree whose time complexity is O (log (log n)) when compared to the time complexity of offline binary search tree model. Online algorithm processes input or data provided piece by piece.