search
Log In
0 votes
381 views

Merging k sorted lists of size n/k into one sorted list of n-elements using heap sort will take how much time ?

My doubt

First approach:- here it is mentioned heap sort so, heap sort will always take nlogn.and here also we have n elements and it will take nlogn.

But other method is to use heap data structure of size k and merge,it will give o(k)+(logk)*(n/k)

I think answer should be nlogn only because the second approach is not heap sort.

Please check.

in Algorithms
edited by
381 views
0
What is head data structure??
0
It was a typo!!
0
By second approach will it not be O(nlogk)????
0
Yes.I mentioned in question itself:)

2 Answers

0 votes
Nlogk will be ans
0 votes

I think here only merging is asked here that means asking for time required for Bulid Heap so time required O(n/k *k)=O(n)

Related questions

7 votes
2 answers
1
1.7k views
Why space complexity of heapsort is O(1)....and why not O(logn)..because of space required by recursion calls which is equivalent to height of the tree...where am i getting wrong plz help...
asked Nov 7, 2016 in Algorithms vineet.ildm 1.7k views
1 vote
1 answer
2
512 views
The number of elements that can be sorted in time using heap sort ?
asked Jul 30, 2016 in Algorithms reena_kandari 512 views
1 vote
1 answer
3
469 views
What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap?
asked Dec 1, 2018 in Algorithms gmrishikumar 469 views
6 votes
3 answers
4
1.7k views
In a min-heap with n elements 1). The 7th smallest element can be found in time, if duplicates are allowed ? 2). The 7th distinct smallest element can be found in time, If duplicates are allowed ?
asked Sep 4, 2016 in Algorithms Kapil 1.7k views
...