patternMinor
Why is subarray $A[p..k-1]$ empty when $k=p$?
Viewed 0 times
emptywhysubarraywhen
Problem
I'm working through a proof of correctness for merge sort.
I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the correctness proof, my textbook says "Prior to the first iteration of the loop, we have $k=p$, so that the subarray $A[p..k-1]$ is empty".
In other words we're saying $A[p..p-1]$ is empty. Suppose $p=1$, then it's saying $A[1..0]$ is empty. Why is this considered empty? Is it just an axiom that subarray $A[a..b]$ is empty if $a>b$?
I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the correctness proof, my textbook says "Prior to the first iteration of the loop, we have $k=p$, so that the subarray $A[p..k-1]$ is empty".
In other words we're saying $A[p..p-1]$ is empty. Suppose $p=1$, then it's saying $A[1..0]$ is empty. Why is this considered empty? Is it just an axiom that subarray $A[a..b]$ is empty if $a>b$?
Solution
It's a convention. One reason for the convention is that the length of an array $A[i..j]$ is $j-i+1$, so if $j=i-1$, we should get an array of length zero. Due to this reason, we sometime consider $A[i..j]$ to be undefined when $j < i-1$; in other cases, the issue does not arise, and $A[i..j]$ is just the empty array whenever $j < i$. In yet other cases, we do not want to allow empty arrays, and then $A[i..i-1]$ is undefined as well.
Since these conventions are not standard (indeed, they are conflicting), if one of them is used, it should be announced beforehand, or when it occurs.
Since these conventions are not standard (indeed, they are conflicting), if one of them is used, it should be announced beforehand, or when it occurs.
Context
StackExchange Computer Science Q#111375, answer score: 2
Revisions (0)
No revisions yet.