Algorithm Question

Question

Comments

the set K will be constant for a given instance hence we just need to build a min heap or max heap which takes O(n) time and accessing K_th smallest elements will take constant time. hence c) O(n)

---

No bro it's wrong, here k is not constant they only given instant for problem understanding.

Here we can use two approaches which is using min heap and selection procedure technique.

By using this ans is coming from my side O(nr)

but ans was given O(n logr)

---

yes i thought so if r is varies then O(n*r) that's what i thought but somehow got convinced because of this https://gateoverflow.in/130879/algorithm-test-2-24 but yeah you are right r varies according to n and it should be O(n.r) but which is not the correct one :/

---

this link doesn't open any question. please check the link.

---

ohh that's because one has to attempt that test to access the question :|

---

Build heap : O(n)

Ex :To find 2nd minimum Delete root 2 times - 2*log(n)

To find rth minimum  - r*log(n)

Total complexity: O(n + r*log(n)) = O(n)

(since r<n and some constant therefore n is asymptotically larger than r*log(n) )

Answer 1

the ans is o(nlogr)  because ....

first we build a heap and then one by one we get logr times required to call and balance it