0
$\begingroup$

I'm currently doing some exercise involving proving the correctness of algorithms.

I often have to write something that resembles:

  • "The element $A[i]$ is smaller than any of the element in the subarray $A[i + 1\dots n]$"
  • "Every element in $A[1\dots i]$ is smaller than any element in $A[i + 1\dots n]$".

I hope to convert the statements into something more concise using mathematical symbols. So far I have thought of

  • $\forall a \in A[i + 1 ... n] ~~ A[i] < a$
  • $\forall a \in A[1 \dots i]~~\not\exists a' \in A[i + 1\dots n]~~ a' \ge a$

but they all seem too complicated for a supposedly Computer Science course.

Is there any notation (e.g. $A[i] < A[i + 1\dots n]$) that is perhaps more standard and less complicated?

$\endgroup$

1 Answer 1

1
$\begingroup$

$\qquad (1)\;\;\;$"The element $A[i]$ is smaller than any of the element in the subarray $A[i + 1\dots n]$."

$$i < t \le n \implies A[i] < A[t]$$

$\qquad (2)\;\;\;$"Every element in $A[1\dots i]$ is smaller than any element in $A[i + 1\dots n]$."

$$1 \le s \le i < t \le n \implies A[s] < A[t]$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .