What does apostrophe-like symbol in the superscript mean?

Question

It's hard to look up the meaning of a symbol if you don't know what it is called in the context that it is written.

That apostrophe-type symbol in the sequence notation - what is that?

Answer 1

That's a prime.

In mathematics, statistics, and science, the prime is generally used to generate more variable names for things which are similar, without resorting to subscripts – $x'$ generally means something related to or derived from $x$.

Answer 2

Draw the character on Detexify or Shapecatcher. Detexify tells you what (La)TeX commands generates a character that looks like what you drew. Shapecatcher tells you what Unicode characters looks like what you drew.

Mathematical notations tend to be easier to find via Detexify. In my first attempt, I got the correct answer \prime as the second choice, with the other choices obviously not right. Although Unicode does have a U+2032 PRIME character, it didn't come up among the many very similar characters that look like a diagonal line.

Once you have the name, you can look it up. Prime has a standard meaning in some fields (in particular calculus, where it means a derivative), but in general it's a way to generate more symbols: $a$ is the name for something and $a'$ is the name for something else; usually there is a relationship between $a'$ and $a$ but it's up to the surrounding text to explain what that relationship is.

Here, $(a'_1, \ldots, a'_n)$ is the sequence produced as output by the algorithm. It is related to $(a_1, \ldots, a_n)$ in that the two contain the same elements but in a different order (i.e. it's a permutation).

Answer 3

The idea here is that the sequence $a'_1,\ldots,a'_n$ is a rearrangement of $a_1,\ldots,a_n$ in non-decreasing order. For example, if the original sequence were $3,1,2,5,4,3$, then the new primed sequence would be $1,2,3,3,4,5$.

The prime ($^\prime$) doesn't have a fixed meaning, and in this particular case, the author could just as well have used a completely new letter for the new sequence, say $b_1,\ldots,b_n$. One common use for the prime is in analysis, where it designates the derivative with respect to some "understood" variable. Another common usage is in linear algebra, where it is sometimes used to denote the transpose (one of several common notations for the transpose, including $^t$ and $^T$).

Answer 4

As well as "prime", well covered by the other answers, the symbol is often pronounced "dash" or "dashed", as in "$x$-dash(ed)" and "$x$-double-dash(ed)" for $x'$ and $x''$, respectively. I've no idea why this is, since the symbol is completely unrelated to the punctuation mark known as a dash ("–").

Answer 5

As Mowji already mentioned, it means a one thing is derived from another.

Think of it as what it come from, the prime used in mathematics, for the a kind of function, named derivative of a function, as in: $f(x) = 2 \times x, f'(x)$ = 2 or another example $f(x) = sin(x), f'(x) = cos(x)$.

The keyword to have in mind sawing this sign is, “derivative” and/or “derived”.