+1 vote
in Data Structures & Algorithms I by (110k points)
What is the time complexity for deleting the string to form a new string in the rope data structure?

(a) O (n^2)

(b) O (n!)

(c) O (log n)

(d) O (1)

This is a very interesting question from Binary Trees in portion Binary Trees of Data Structures & Algorithms I

This question was posed to me in my homework.

1 Answer

+1 vote
by (672k points)
selected by
Best answer
Correct choice is (c) O (log n)

For explanation: In order to perform the deletion on the rope data structure, one can delete the given string at any position x to form a new string in O (log n) time. So, the time complexity for worst case is O (log n). This can be done by two split operations and one concatenation operation.

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.