Problem 1.3 seems correct, but justification seems wrong

[rdgifford]

The justification to problem 1.3 isn't squaring up for me: For n=2 and k=4, (2*4(4 - 1)/ 2) = 12. But here's what I expect: merge 1: 2 + 2 merge 2: 4 + 2 merge 3: 6 + 2 total: 18 operations

What gives? Thank you in advance!

[GuifuLiu]

When I am attempting 1.3, this is my understanding: (Please point it out if I am wrong) Every time a merge is called, the worst case scenario is that all elements involved needed to compare with one another, leaving a complexity of n (for n is the length of merged sub-array) Therefore, For k = 4, the complexity would be (2+3+4)n. For k = 5, the complexity would be (2+3+4+5)n. Therefore, for any k, the complexity would be (2+...+k)n = 0.5(2+k)(k-1)n Approximately n*k^2