Useful read for 1st statement

https://stackoverflow.com/questions/5380568/algorithm-to-find-k-smallest-numbers-in-array-of-n-items

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+4 votes

0

Useful read for 1st statement

https://stackoverflow.com/questions/5380568/algorithm-to-find-k-smallest-numbers-in-array-of-n-items

+1 vote

Best answer

0

@Manu,

for (ii), i think it will take O(n+klogn)........

since n/2 minimum elements are present in leaves of a max heap, now you have to find kth minimum among them, you can work it like this,

create min heap for that n/2 elements -> O(n)

perform extract_min for k times -> O(klogn)

in total it will take-> O(n+klogn), though if k is some constant, answer will be O(n), but in worst case k can be of O(n)..

therefore i think in worst case to find kth min in max heap will take -> O(n+klogn)

0

and also one more thing, it might be case that kth min is not even in leaf, because leaf contains about n/2 keys, what if it is saying to find (n/2+5)th minimum..

0

@nitish yes you are right answer should b O(n + klogn)

but they explicitly mentioned that k is less than n, and if we believe that it's some constant and n value is huge, we can go for O(n) T.C

but they explicitly mentioned that k is less than n, and if we believe that it's some constant and n value is huge, we can go for O(n) T.C

0

but less than doesn't mean that it is some constant, k could be {n-4, n-6 , n/2 , n/4}, all these values are <n and also even O(n)

0

for that case take all n elements of max heap and build a min heap...and then perform kth min. operation...

**T(n)=O(n)+O(klogn) **

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,756 questions

52,850 answers

183,548 comments

68,742 users