# Appendix A: Review of Necessary Mathematics Except for the material that is marked or  this text does not require that you have a strong background in mathematics. In particular, it is not assumed that you have studied calculus. However, a certain amount of mathematics is necessary for the analysis of algorithms. This appendix reviews that necessary mathematics. You may already be familiar with much or all of this material. ## A.1 Notation Sometimes we need to refer to the smallest integer that is greater than or equal to a real number *x*. We denote that integer by ⌈*x*⌉. For example,  We call ⌈*x*⌉ the ***ceiling*** for *x*. For any integer *n*, ⌈*n*⌉ = *n*. We also sometimes need to refer to the largest integer that is less than or equal to a real number *x*. We denote that integer by ⌊*x*⌋. For example,  We call ⌊*x*⌋ the ***floor*** for *x*. For any integer *n*, ⌊*n*⌋ = *n*. When we are able to determine only the approximate value of a desired result, we use the symbol ≇, which means "equals approximately." For example, you should be familiar with the number π, which is used in the computation of the area and circumference of a circle. The value of π is not given by any finite number of decimal digits because we could go on generating more digits forever. (Indeed, there is not even a pattern as there is in ⅓ = 0.3333333….) Because the first six digits of π are 3.14159, we write  We use the symbol ≠ to mean "does not equal." For example, if we want to state that the values of the variables *x* and *y* are not equal, we write  Often we need to refer to the sum of like terms. This is straightforward if there are not many terms. For example, if we need to refer to the sum of the first seven positive integers, we simply write  If we need to refer to the sum of the squares of the first seven positive integers, we simply write  This method works well when there are not many terms. However, it is not satisfactory if, for example, we need to refer to the sum of the first 100 positive integers. One way to do this is to write the first few terms, a general term, and the last term. That is, we write  If we need to refer to the sum of the squares of the first 100 positive integers, we could write  Sometimes when the general term is clear from the first few terms, we do not bother to write that term. For example, for the sum of the first 100 positive integers we could simply write  When it is instructive to show some of the terms, we write out some of them. However, a more concise method is to use the greek letter Σ, which is pronounced ***sigma***. For example, we use Σ to represent the sum of the first 100 positive integers as follows:  This notation means that while the variable *i* is taking values from 1 to 100, we are summing its values. Similarly, the sum of the squares of the first 100 positive integers can be represented by  Often we want to denote the case in which the last integer in the sum is an arbitrary integer *n*. Using the methods just illustrated, we can represent the sum of the first *n* positive integers by  Similarly, the sum of the squares of the first *n* positive integers can be represented by  Sometimes we need to take the sum of a sum. For example,  Similarly, we can take the sum of a sum of a sum, and so on. Finally, we sometimes need to refer to an entity that is larger than any real number. We call that entity ***infinity*** and denote it by ∞. For any real number *x*, we have