Problem 1.3 seems correct, but justification seems wrong

amolnayak311 / algorithms-illuminated

My notes for Tim Roughgarden's awesome course on Algorithms and his 4 part books

159 stars 54 forks source link

Problem 1.3 seems correct, but justification seems wrong #3

Open rdgifford opened 4 years ago

rdgifford commented 4 years ago

The justification to problem 1.3 isn't squaring up for me: $n + 2n + 3n =n(1 + 2 + 3) = nk(k - 1) / 2 \approx nk^2$ 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 commented 4 years ago

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