You are viewing a single comment's thread. Return to all comments →
@dragan_ostojic, thank you for this explanation, it's clear and easy to follow.
One question: You can use the same argument used to eliminate (min-5) as a viable target to also eliminate (min-3) and (min-4). Stated differently:
Let (min-3) >= 0 such that [min-3 min-3 ... min-3] is a valid non-negative target.
delta'' = [v0 - (min-3) ... vn-1 - (min-3)] = [v0 - min + 3 ... vn-1 - min + 3]
Compared to our original target of [min ... min], and
delta = [v0-min ... vn-1 - min],
it's clear that delta'' results in 2n more operations than delta. Therefore, we should not need to consider (min-3).
Similarly, we shouldn't need to consider (min-4), because
delta''' = [v0 - min + 4 ... vn-1 - min + 4] results in 2n more operations than
delta = [v0-min ... vn-1 - min].
So my question: Isn't it sufficient to check ONLY for (min), (min-1) and (min-2)?
Equal
You are viewing a single comment's thread. Return to all comments →
@dragan_ostojic, thank you for this explanation, it's clear and easy to follow.
One question: You can use the same argument used to eliminate (min-5) as a viable target to also eliminate (min-3) and (min-4). Stated differently:
Let (min-3) >= 0 such that [min-3 min-3 ... min-3] is a valid non-negative target.
delta'' = [v0 - (min-3) ... vn-1 - (min-3)] = [v0 - min + 3 ... vn-1 - min + 3]
Compared to our original target of [min ... min], and
delta = [v0-min ... vn-1 - min],
it's clear that delta'' results in 2n more operations than delta. Therefore, we should not need to consider (min-3).
Similarly, we shouldn't need to consider (min-4), because
delta''' = [v0 - min + 4 ... vn-1 - min + 4] results in 2n more operations than
delta = [v0-min ... vn-1 - min].
So my question: Isn't it sufficient to check ONLY for (min), (min-1) and (min-2)?