Editor">
Editor Staff asked 5 months ago
Editor Staff asked 5 months 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 5 months ago
Editor Staff answered 5 months 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).
