What is the upper bound for a tango tree if k is a number of interleaves?

Category: QuestionsWhat is the upper bound for a tango tree if k is a number of interleaves?
Editor">Editor Staff asked 4 weeks ago

What is the upper bound for a tango tree if k is a number of interleaves?
 
(a) k+2 O (log (log n))
 
(b) k O (log n)
 
(c) K^2 O (log n)
 
(d) k+1 O (log (log n))
 
My doubt is from Binary Trees topic in chapter Binary Trees of Data Structures & Algorithms I
 
This question was posed to me during a job interview.

1 Answers
Editor">Editor Staff answered 4 weeks ago

The correct choice is (d) k+1 O (log (log n))
 
Best explanation: Upper bound is found to analyze the work done by a tango tree on a given set of sequences. In order to connect to the tango tree, the upper bound is found to be k+1 O (log (log n)).