i have a program that run merge on sorted arrays
each array is in size n and i have k arrays
by dividing to 2 until merge receive only 2 arrays merge them and then merge 2 bigger arrays i found that my complexity is:
t(nk)=2(t(k/2)) + cnk
what is the running time complexity?
guyeyal 0 Newbie Poster
davidrafter 0 Newbie Poster
Use the Master theorem to solve this; it's on Wikipedia and in a number of textbooks.
prime1999 12 Newbie Poster
The equation you gave, if the first term is corrected to t(k), should give a complexity of O(nk log k). Another algorithm that could do this was to use a heap -- it was so that you could get the elements of the final array in order -- so the complexity was O(m log k) where m is the number of smallest elements you want in the final array, and you do not need to have the k arrays to be of a certain size.
for each array as F: heap_insert(read_next(F),F);
while heap_pop_min as (M,X): output(M); heap_insert(read_next(X),X);
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.