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 (a1, a2, … , an) is any sequence (s1, s2, … , sk) such that
s1 = ai1, s2 = ai2, … , sk = aik
for some sequence i1 < i2 < … < ik 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[i1], s[2] = a[i2], … , s[k] = a[ik]
for some sequence i1 < i2 < … < ik 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
(a1,
a2,
… ,
an)
is any sequence of the form
(ai,
ai+1,
ai+2,
… ,
ak)
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 X endowed with the following property: every element of X belongs to one and only one of the elements of P. Each element of P is a block of the partition.
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 log2 n , that is, the real number x such that 2x = n. (By the way: the correct notation is log2 n, not log 2 n, not log 2n, and not log2 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…)