We wish to characterize these resource requirements as functions of one or more of the "essential parameters" (from the standpoint of the resource to be measured) describing the data operated on by the algorithm. Such parameters might include the size of an array (for example, finding the minimum entry takes time depending primarily on the number of entries in a list), the size of a number (for example, the time required to raise a real number to an integral power depends primarily on the absolute value of the exponent), and the number of processors (if a parallel computer is used).

The interesting questions in analysis of algorithms usually are concerned with values of the "essential parameters" that tend to make an algorithm run slowly -- for example, n tending to infinity, if n is the size of a list to be sorted. If n is small, even an inefficient (correct) algorithm may yield the desired result in acceptable time. However, for large n, there may be, for example, an enormous performance difference between the "Quick Sort" method and the equally correct but slower "Bubble Sort" method. The problem, roughly speaking, is to describe the running time of the algorithm as being approximately proportional to some simple function of the "essential parameters" -- for example, sorting a list of size n on a serial computer takes, on average, time proportional to

The mathematical tools needed for the analysis of running times typically include mathematical induction and related analysis of recursive relations, and tools from advanced calculus such as the relation between the definite integral and area, L'Hopital's Rule, summation of infinite series, and other limit theorems "at infinity."

The reader should be attempt to prove the following: 

• arithmetic operations (addition, subtraction, multiplication, division, negation, exponentiation IF THE EXPONENT IS BOUNDED)

• bit operations (left or right shift; bitwise AND, OR, XOR, NOT; etc.)

• unary and binary boolean operations (NOT, AND, OR)

• comparisons ( =, <>, <, <, >, > )

• reading a unit of information from memory, or (in a parallel computer) from a message sent by an adjacent processor

• writing a unit of information to memory, or (in a parallel computer) in a message sent to an adjacent processor

• branching (GOTO, loop control, call upon or return from subprogram, IF or switch/CASE control)

Strictly speaking, these are not all realistic assumptions. For example, one might argue that some arithmetic operations take time proportional to the number of bits used for the operands, so that, e.g., addition of integers of small absolute value is faster than addition of integers of huge absolute value. In practice, however, the above are fairly realistic, as the operations cited are both fundamental and fast, and we are usually more concerned with how the running time of an algorithm depends on the quantity of data being processed than in how it depends on the running times of elementary operations. 

When it is reasonable to assume the arguments of the functions are suitably restricted, evaluation of mathematical functions such as logarithms and exponentials, trigonometric and inverse-trigonometric functions, etc., are regarded as having Θ(1) running times. When such functions are considered to have unbounded arguments, their running times typically depend in non-constant fashion on their arguments. E.g., consider two different algorithms for computing the n-th power of a real number: one, based on repetitive multiplication by the base of the exponentiation, requires Θ(n) time (and Θ(1) memory); another, based on repetitive squaring, requires Θ(log n) time (and Θ(log n) memory).

Since a program consists of a series of instructions, we need the following rules to analyze the running time of a piece of code:

1.     If Instruction A requires Θ(f(n)) time and Instruction B requires Θ(g(n)) time, then Instruction A followed by Instruction B requires Θ(f(n)+g(n)) time.

Often, the above simplifies nicely, since

Θ(f(n)+g(n)) = Θ("long-term max"{f(n), g(n)}) (*)

when the right-hand side of (*) makes sense. The reader is encouraged to prove each of the following without using (*):

o Θ(1 + 1) = Θ(1); (yes, 2 = Θ(1))

o Θ(n² + n) = Θ(n²);

o Θ(n + log n) = Θ(n).

o Now prove (*) after determining the meaning of "when the right-hand side of (*) makes sense."

2.     If the body of a loop requires Θ(f(n)) time and the loop body is performed Θ(g(n)) times, then completion of the loop (all its performances of the loop body) requires Θ(f(n)*g(n)) running time.

We may obtain similar rules for Ω and O notation.