The Gateway to Computer Science Excellence
+2 votes
313 views

in Algorithms by Active (2k points) | 313 views
0

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 Kth smallest elements will take constant time. hence c) O(n)

+1
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)
+1

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 :/

0
this link doesn't open any question. please check the link.
0
ohh that's because one has to attempt that test to access the question :|
0
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) )

1 Answer

0 votes
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
by (27 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,367 answers
198,497 comments
105,265 users