Why is iterative k-way merge O(nk^2)?

Because it doesn’t traverse each of the k arrays once. The first array is traversed k-1 times, the first as merge(array-1,array-2), the second as merge(merge(array-1, array-2), array-3) … and so on.

The result is k-1 merges with an average size of n*(k+1)/2 giving a complexity of O(n*(k^2-1)/2) which is O(nk^2).

The mistake you made was forgetting that the merges are done serially rather than in parallel, so the arrays are not all size n.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)