recursion complexity

[guyeyal]

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?

[davidrafter]

Use the Master theorem to solve this; it's on Wikipedia and in a number of textbooks.

[prime1999]

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