• 0

Time complexity of a datastructure by number of operations
  • sortedarray
  • array
  • general
  • searching
  • timecomplexity
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (3215)

Suppose you are asked to implement a data structure that maintains a collection of items allowing operations such as insert , delete and search . Assume that you chose an ordered array for your data structure. Your data structure is implemented in an application that starts with an empty collection of items and performs insert operation followed by some search operations. It is seen that the number of insert operation is \( O(logn) \) and that of search is \( O(n) \) where n is the size of input in that application. From these data, what would be the total worst case running time of all operations performed by your data structure, as a function of n ?


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

Since the number of insert operation is \( O(logn) \) , there are \( O(logn) \) elements in the ordered array. In the worst case, each insert operation takes linear (in the number of elements in the array) time. So, each insert takes \( O(logn) \) time.
Therefore, total running time for insert = \( O(logn \times logn) \).

Since the items are ordered, search can be implemented using binary search. In the worst case, binary search takes logarithmic (to the number of input items) time. So, in the worst case, search operation takes \( O(log(logn)) \). To perform n such operations, total running time = \( O(n \times log(logn)) \).
Therefore, total running time of the datastructure (for insert and \( search \)) is \( O(n \times log(logn)) + O(logn \times logn) = O(n \times log(logn)) \).
You need to Sign In to post your solution.