What is the time complexity for splitting the string into two new string in the rope data structure?

Category: QuestionsWhat is the time complexity for splitting the string into two new string in the rope data structure?
Editor">Editor Staff asked 1 month ago

What is the time complexity for splitting the string into two new string in the rope data structure?
 
(a) O (n^2)
 
(b) O (n!)
 
(c) O (log n)
 
(d) O (1)
 
This intriguing question comes from Binary Trees topic in portion Binary Trees of Data Structures & Algorithms I
 
I got this question in final exam.

1 Answers
Editor">Editor Staff answered 1 month ago

Correct choice is (c) O (log n)
 
To explain: In order to perform the splitting on the rope data structure, one can split the given string into two new string S1 and S2 in O (log n) time. So, the time complexity for worst case is O (log n).