The word *positive* is often somewhat ambiguous:
does it mean > 0
or ≥ 0?
Something similar goes for the word *negative*.

In this site,
a number `x` is considered positive
if `x` ≥ 0
and strictly positive
if `x` > 0.
(We may occasionally use the redundant expression
*positive or null*,
for emphasis.)

Similarly,
a number `x` is negative
if `x` ≤ 0
and strictly negative
if `x` < 0.

An array `v[0..n-1]`
is increasing
(or is in increasing order)
if

`v[0]` ≤
`v[1]` ≤
. . . ≤
`v[n-1]` .

The array is
strictly increasing if
we have <

in place of
≤

.
The concepts of *decreasing* and
*strictly* decreasing are defined
similarly.

Analogous definitions apply to sequences and to linked lists.

Caution:
Some books say
nondecreasing

where we say increasing

.
They also say
increasing

where we say strictly increasing

.

A sequence is characterized by the order of its elements:
there is a first element, a second element, etc.,
a last element.
(Example: the sequence of digits of a phone number.)
To specify the elements of a sequence,
write them, in order, wrapped in parentheses: (`a`, `b`, `c`, …).
If this does not cause confusion,
you may omit the parentheses and commas
and write simply `a` `b` `c` …

A set has no order.
There is no first element
and no last element.
(Example: the set of numbers in a lottery result.)
As a consequence, a set has no repeated

elements.
To specify the elements of a set,
write them, in any order,
wrapped in curly braces: {`a`, `b`, `c`, …}.

We shall use the notation `a` . . `b`
to designate the set of integers {`a`, `a`+1, `a`+2, … ,
`b`}.
Depending on the context, this notation can also designate
the *sequence* (`a`, `a`+1, `a`+2, … , `b`).

A permutation
of a finite sequence
is any sequence that has the same elements
in a possibly different order.
For example,
2 1 4 3
is a permutation of
1 2 3 4 .
A sequence with `n`
elements has exactly `n`! different permutations.

A subsequence
is what is left after some terms of a sequence
are deleted.
More precisely,
a subsequence
of a sequence
(`a`_{1},
`a`_{2},
… ,
`a`_{n})
is any sequence
(`s`_{1},
`s`_{2},
… ,
`s`_{k})
such that

`s`_{1} = `a`_{i1},
`s`_{2} = `a`_{i2},
… ,
`s`_{k} = `a`_{ik}

for some sequence
`i`_{1} <
`i`_{2} <
… <
`i`_{k}
of indices.
For example,
(2, 3, 5, 8)
is a subsequence of
(1, 2, 3, 4, 5, 6, 7, 8).

The concept of subarray is essentially the same,
since an array is essentially the same as a sequence.
Hence,
a subarray of an array
`a`[1 .. `n`]
is any array
`s`[1 .. `k`]
such that

`s`[1] = `a`[`i`_{1}],
`s`[2] = `a`[`i`_{2}],
… ,
`s`[`k`] = `a`[`i`_{k}]

for some sequence
`i`_{1} <
`i`_{2} <
… <
`i`_{k}
of indices.
If `k` = 0,
the subarray is empty.

A segment
of a sequence is a continuos

subsequence.
In other words, a segment
is what is left after some of the *initial* terms
and some of the *final* terms
of the sequence are deleted.
(In some contexts, a segment is referred to as a *run*.)
More precisely,
a segment
of a sequence
(`a`_{1},
`a`_{2},
… ,
`a`_{n})
is any sequence of the form
(`a`_{i},
`a`_{i+1},
`a`_{i+2},
… ,
`a`_{k})
where
1 ≤ `i` ≤ `k` ≤ `n`.
For example,
(2, 3, 4, 5)
is a segment of
(1, 2, 3, 4, 5, 6, 7, 8).

Similarly,
a segment
of an array
`a`[1 .. `n`]
is any array of the form
`a`[`i` .. `k`]
where
1 ≤ `i` ≤ `k` ≤ `n`.
If `i` > `k`,
the expression
`a`[`i` .. `k`]
represents the empty segment.

A prefix of a sequence is a segment that contains the first term of the sequence. A suffix of a sequence is a segment that contains the last term of the sequence.

A partition
of a set `X`
is any collection ** P**
of nonempty subsets of

Example:
{{1,3},{2,4,7},{5},{6,8}}
is a partition of
{1,2,3,4,5,6,7,8}.
The set {6,8} is one of the blocks of the partition.
(Please do not say
the set {6,8} is a partition of {1,2,3,4,5,6,7,8}.

)

The floor of a real number `x`
is the result of rounding `x` down.
In other words,
the floor of `x` is the only integer `i` such that

`i` ≤ `x`
< `i` + 1 .

For example, the floor of 3.99 is 3.
Em C notation, we can denote the floor of `x`
by
`(int) x` ,
provided `x` is not strictly negative.
In more traditional notation,
the floor of `x` is denoted by

⌊ `x` ⌋ .

The ceiling of a real number `x`
is the result of rounding `x` up.
In other words,
the ceiling of `x` is the only integer `j` such that

`j` − 1 < `x`
≤ `j` .

For example, the ceiling of 3.01 is 4.
In traditional notation,
the ceiling of `x` is denoted by

⌈ `x` ⌉ .

Our logarithms are always taken to the base 2.
Hence, log `n`
is a shorthand for log_{2} `n` ,
that is,
the real number `x` such that 2^{x} = `n`.
(By the way: the correct notation is log_{2} `n`,
not log 2 `n`,
not log 2^{n},
and not log_{2}^{ n} .)

Therefore,
log `n`
is essentially equal to the number of bits
in the binary representation of `n`,
i.e., approximately 3.3 times the number of digits
in the decimal representation of `n`.

(Our notation is in conflict with the notation of the
`math` library
of C,
where the function `log` produces the *natural* logarithm,
that is,
the logarithm to the base `e` = 2.71828…)