Question about odd-even sort
Closed this issue · 4 comments
In the lecture, when we prove CE_i-1 <= CO_i+1, we use a lemma:
for all i, there is j s.t. AE_j <= CE_i <= AE_j+1, BE_i-j <= CE_i <= BE_i-j+1
like this: CE_i-2 <= max(AE_j-1,BE_i-j-1)
<= max(AO_j,BO_i-j)
<= max(CO_i,CO_i) = CO_i
in here CE_i-2 <= max(AE_j-1,BE_i-j-1) ,
we use AE_j-1, not AE_j+1 because we use CE_i-2, not CE_i
But in lecture, when we prove CE_i <= CO_i+2, we use lemma:
for all i, C_i=min_j(max(A_j,B_i−j)).
like this: Co[i+ 2] = max(Ao[j],Bo[i+ 2−j])(for somej, by lemma)
≥ max(Ae[j−1],Be[i+ 1−j])(by def. ofAe,Ao,Be,andBo)
≥ Ce[i].
in here Co[i+ 2] = max(Ao[j],Bo[i+ 2−j]),
we use Ao[j], not A[j+2].
I think both are have not i. but I don't know why in lecture, we minus in A also, and in lecture note, we didn't add in A. I couldn't find the reason. could somebody let me know the reason?
shortly,
in lecture proof, we use AE_j-1 not AE_j+1 because we did -2 at CE_i in CE_i-2 <= max(AE_j-1,BE_i-j-1). but in lecture note, when we did +2 at Co[i], we didn't add at Ao[j].
so I have confusion. help me..
The proof in the class differs from that in the lecture note. I prefer the lecture note one, because it's simpler.
then, what make the difference? I mean..
CE_i-2 <= max(AE_j-1,BE_i-j-1) why in here we can minus 2 to AE_j+1?
I think we can't minus 2 here also for same reason with Co[i+ 2] = max(Ao[j],Bo[i+ 2−j]).
Hmm... Probably we're exploiting the fact that (1) i-2 = j-1 + i-j-1, and (2) for all x,y, CE_(x+y) <= max(AE_x, BE_y). But I recommend you to study the proof in the lecture note, because it's better.
aha! Thank you!