recursion complexity

Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
Reply

Join Date: Jul 2009
Posts: 1
Reputation: guyeyal is an unknown quantity at this point 
Solved Threads: 0
guyeyal guyeyal is offline Offline
Newbie Poster

recursion complexity

 
0
  #1
Jul 6th, 2009
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?
Reply With Quote Quick reply to this message  
Join Date: Mar 2009
Posts: 5
Reputation: davidrafter is an unknown quantity at this point 
Solved Threads: 1
davidrafter davidrafter is offline Offline
Newbie Poster

Re: recursion complexity

 
0
  #2
Jul 6th, 2009
Use the Master theorem to solve this; it's on Wikipedia and in a number of textbooks.
Reply With Quote Quick reply to this message  
Join Date: Jul 2009
Posts: 9
Reputation: prime1999 is an unknown quantity at this point 
Solved Threads: 0
prime1999 prime1999 is offline Offline
Newbie Poster

Re: recursion complexity

 
0
  #3
Jul 17th, 2009
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);
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC