Footnotes: Mathematics


Positive and negative

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.


Increasing sequences, arrays, and lists

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.


Sequences vs sets

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).


Permutations

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.


Subsequences and subarrays

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 = ai1s2 = 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.


Segments

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 ≤ ikn.  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 ≤ ikn.  If i > k, the expression a[i .. k] represents the empty segment.


Prefixes and suffixes

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.


Partitions

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}.)


Floor and ceiling

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 ⌉ .


Base 2 logarithms

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  log2n,  not  log 2 n,  not  log 2n,  and not  log2n.)

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…)