Algorithm Complexity: Sorted Arrays into Sorted Array
View Single Post
Mar8-12, 09:12 PM
OK, but in one type of optimized case, there are k n copies done and in the worst case, (k) (k-1) n = (k
- k) n compares done, how do you balance the copies versus compares for O(...) in this case?
How did you get these numbers?
By merging k lists at the same time (one type of optimized case), k n elements copied, k-1 compares (worst case) for each element copied. This would be one of the "less expensive" implementations mentioned at the end of the original post.