CHAPTER 3

Algorithms, Integers

3.1. Algorithms

In general an algorithm is a finite list of instructions with the following characteristics:

1. Precision. The steps are precisely stated.

2. Uniqueness. The result of executing each step is uniquely determined by the inputs and the result of preceding steps.

3. Finiteness. The algorithm stops after finitely many instructions have been executed.

4. Input. The algorithm receives input.

5. Output. The algorithm produces output.

6. Generality. The algorithm applies to a set of inputs.

Basically an algorithm is the idea behind a program. Conversely, programs are implementations of algorithms.

3.1.1. Pseudocode.

Pseudocode is a language similar to a programming language used to represent algorithms. The main difference respect to actual programming languages is that pseudocode is not required to follow strict syntactic rules, since it is intended to be just read by humans, not actually executed by a machine.

3.1.2. Recursiveness.

Recursive Definitions. A definition such that the object defined occurs in the definition is called a recursive definition

1. A Basis, where the function is explicitly evaluated for one or more values of its argument.

2. A Recursive Step, stating how to compute the function from its previous values.

Recursive Procedures. A recursive procedure is a procedure that invokes itself. Also a set of procedures is called recursive if they invoke themselves in a circle. A recursive algorithm is an algorithm that contains recursive procedures or recursive sets of procedures.

3.1.3. Complexity.

In general the complexity of an algorithm is the amount of time and space (memory use) required to execute it. Here we deal with time complexity only.

1. Best-case time: minimum time needed to execute the algorithm among all inputs of a given size n.

2. Wost-case time: maximum time needed to execute the algorithm among all inputs of a given size n.

3. Average-case time: average time needed to execute the algorithm among all inputs of a given size n.

Big Oh Notation. A function f(n) is said to be of order at most g(n), written f(n) = O(g(n)), if there is a constant C1 such that |f(n)| C1|g(n)| for all but finitely many positive integers n.

Omega Notation. A function f(n) is said to be of order at least g(n), written f(n) = (g(n)), if there is a constant C2 such that |f(n)| C2|g(n)| for all but finitely many positive integers n.

Theta Notation. A function f(n) is said to be of order g(n), written f(n) = (g(n)), if f(n) = O(g(n)) and f(n) = (g(n)).