GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 9

Answer 1

We will first find $n/2$ largest element (or median) and then we can use the partition method from quick sort to put this median at the correct place.

This will take $\theta(n)$.

Now we will find  $n/4$ largest element. But here is a good news. You do not need to check all $n$ elements, you can just check the subarray left of the median. Which are $n/2$ elements only. Now again you need the median of these $n/2$ elements.

We have a recurrence here:

$T(n) = T(n/2) + \theta(n)$

We get $\theta(n)$ as the answer.

Answer 2

This is what I think : 

→ Array is unsorted we need (n/2)^th largest element : $\Theta$(n) when k = n/2

→ Now we apply partition algorithm with this (n/2)^th element as pivot : $\Theta$(n)

→ Now at this time all the element larger than our pivot is on left hand side right !

Now just call the function again for left hand side : 

T(n) = T(n/2) + $\Theta$(n) + $\Theta$(n)

        ≈ T(n/2) + $\Theta$(n)

        ≈ $\Theta$(n)

---

$\Theta$(n) +  $\Theta$(n/2) + $\Theta$(n/4) + …..logn times

n + n/2 + n/4 + … log(n) times = n * (1 + 2 + 4 + .. logn) = n * ((1/2)^(logn) – 1) = n * (1 – 1/n) ≈ n – 1 ≈ $\Theta$(n) 

Comments

@Sachin Mittal 1 sir, please check this.

Thank you.🙂

---

That is correct but please consider putting this as a comment to the original answer.
Your answer is correct but does not add much  w.r.t selected answer.
Hence it is better to put it as a comment.

Answer 3

Sir can we approach in this way??

let at first we make max heap which takes O(n)

then we search the elements

                1st  largest takes – 0 comparison

                 2nd  largest take – 1comparison 

                4th  largest takes – 2 comparisons (because 3rd largest worst case at level 3)

                 .

                 .

               nth largest will take n-1 comparison

total comparison = ∑(n-1)[total logn number fo terms]

                            =$\frac{logn(logn-1)}{2}$

                            =O((logn)$^{2}$)

final complexity=O(n)[for building max heap]+O((logn)$^{2}$)[for comparison]

                         =O(n)

Comments

we are finding till median element so there for total comparison should be [n/2*(n/2 +1)]/2

am i correct?