in DS
131 views
2 votes
2 votes
Can anyone please explain how to find “ i “ smallest elements from an array whose elements are distinct

Please use max heap to explain the working

input : n distinct elements

output : i smallest elements
in DS
131 views

1 Answer

4 votes
4 votes
Best answer

Using max heap we can find i smallest elements in O( n * log i ) time

this method is very popular in coding interviews

selected by

4 Comments

@[ Jiren ] Nice answer 

thank you ;)

0
0
We have taken 'i'  to be constant right?  That's why we r going from O((n-i) logi + i)  to O(n(logi)).. Right?
0
0

@KartikGawande 

NO

Even if i depends on “n” like i = n

the time complexity still wont exceed n*logi because (n-n)*logi+n = n which is O(nlogn) 

Also remember that we cant take any parameter as constant unless mentioned in Algorithms and Data Structures

But writing Θ( n*logi ) is wrong we should write Θ( (n-i) logi + i )

2
2
@[ Jiren ] i see
0
0

Related questions

1 vote
1 vote
1 answer
1