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 ?
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. |