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)**

The Gateway to Computer Science Excellence

+2 votes

0

_{th }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)

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,395 answers

198,595 comments

105,446 users