retagged by
1,839 views
2 votes
2 votes

Consider the following possible data structures for a set of $n$ distinct integers.

  1. A min-heap
  2. An array of length $n$ sorted in increasing order
  3. A balanced binary search tree

For which of these data structures,  the number of steps needed to find and remove the $9^{th}$ largest element in $0 (\log n)$ time in the worst case?

  1. I and III
  2. II and III
  3. I and II
  4. II only
retagged by

3 Answers

Best answer
2 votes
2 votes

For Min Heap - It will take O(n) in worst case .

For Array which is sorted in increasing order  : Finding the 9th largest element is O(1). The array is sorted so there is no need for rearrangement. Removing the 9th largest element is also O(1), so all-in-all the worst case is O(log n)  .

For Balanced Binary Search Tree - If h is the height of the tree, then  the 9th largest element will be in the rightmost sub-tree at height h - 4.  

Now, to find a particular node ( here 9th node ) we need to perform one comparison on each level, or maximum of ( h+1) comparisons are required.

we have total n nodes, so 2h+1 - 1 = n 

so h = log2 ( n + 1 ) - 1 

This means, that a “balanced” BST with  nodes has a maximum order of log n levels, and thus it takes at most log n comparisons to find a particular node. 

So it takes O (logn) in worst case.

Hence option B is correct ,  II and III are true.

selected by
5 votes
5 votes

Short answer

Option B — because 9th largest element is asked for.

Min heap is centralized towards smaller elements, so for larger elements, time complexity is never optimal.

For a sorted array, all we need to do is go to the 9th element from the last index. Extract it, then shift 8 elements one position to the left. This takes constant time.

For balanced BST, the largest element is the rightmost element. Combine that with the fact that the tree is balanced, we get logarithmic time complexity.


Long Answer

find and remove the 9th largest element

First of all, note that Time Complexity is a theoretical concept, and there's a world of difference between "9th largest" and "kth largest"

Let's see this question for both 9th largest, and kth largest — for each data structure given. Along with a few other variations.


Min heap

In a min heap, we know only three things:-

  1. Root has the smallest element.
  2. Root of a subtree has the smallest element of that subtree. Both these points are the definitions of "heap property"
  3. The nth smallest element will be found in the first n levels of the min heap.

(For max heap, all the points apply for "largest" instead of smallest)

So, do we know anything about the largest element in a min heap? Other than the fact that it will be a leaf node (can be derived from heap property), we can't say anything more.

The 9th largest element will be in any random location, as long as it doesn't violate heap property. This will take O(n) time. Same would be for the case of kth largest element.

 

PS: If this was a max heap, then by point number 3, we know that 9th largest element will be present in the first 9 levels. So, finding the 9th largest element in any max heap takes $O(1)$ time. Because no matter how big the heap is, we'll search for only first 9 levels.


Sorted Array

In a sorted array of n elements, all we need to do is go to the 9th element from the last index. Extract it, then shift 8 elements one position to the left. This takes $O(1)$ time.

But if this was kth largest, then we'd have needed to go to the kth element from the right, extract it, and move $(k-1)$ elements to the left. This would take $O(k)$ time.

For the smallest element, we would extract the element at the first index (index number 0) and move the remaining $(n-1)$ elements by one position to the left. This takes $O(n)$ time.

Keep in mind this we're doing this rearrangement because we need to find and remove the required element.


Balanced Binary Search Tree

This is a bit tricky. But any problem related to Balanced Binary Search Tree should be solved by keeping this fact in mind that to find any specific node, we need $O(logn)$ time.

We'll get the largest element in $O(logn)$ time. Remove it, and re-adjust: $O(logn)$ time.

So, total time to find and remove the largest element: $O(logn+logn)=O(logn)$

If we do this 9 times, we get $O(18logn)=O(logn)$ time.

 

Obviously, this algorithm rips apart your tree, and is meant to be used just once. Or you can add back the 9 elements, again in $O(9logn)=O(logn)$ time.

1 votes
1 votes
Doubt in II. array part

if we remove element 9th from array, we need to shift all remaining elements after 9th element. This will take O(n) time.

Can any one explain.
Answer:

Related questions

1 votes
1 votes
1 answer
1
Bikram asked Jan 24, 2017
308 views
Suppose that six keys are inserted into an unbalanced binary search tree in the following order: $4, 6, 3, 8, 2$, and $5$.Then which of the following statements is/are co...
2 votes
2 votes
2 answers
2
1 votes
1 votes
1 answer
3
Bikram asked Jan 24, 2017
258 views
Which of the following sorting algorithms has the lowest best-case asymptotic algorithmic complexity?Selection sortMerge sortInsertion sortHeap sort