algorithms and complexities

2. On-line median In class, we discussed the on-line kth largest problem. We solved it, using an augmented AVL-tree structure, with the following characteristics: Insert(x) i e. the number of Insert operations, minus the number of Delete operations, up until now) in time and space O(logan) where n is the number of elements in the structure at this time Delete(x) in time and space O(log,n) where n is the number of elements in the structure at this time (i e. the number of Insert operations, minus the number of Delete operations, up until now). Findk) in time O(log,n) and space O(1) where n is the number of elements in the structure at this time (i e, the number of Insert operations, minus the number of Delete operations, up until now) Suppose that instead of doing the Find(k) operation, with k an arbitrary positive integer that can vary from one Find to the next, we replace it by Findi n/3) where n is the number of all elements that are currently stored in the structure Can you devise a data structure and algorithms for Insert(x) Delete(x) Find n3) which improve over the Find(k) approach discussed in class. (Obviously, that approach will still apply, so we know that all three operations can certainly be done in time and space O(logan); however, the question for you to solve is: Can you do better). Carefully formulate your data structure, outline the three algorithms in some detail, and determine with care the time and space complexities of your three algorithms different Do not repeat everthing)