In algorithmic analysis, one is interested in the amount of resources used by an algorithm and in the algorithm's correctness. The time complexity measures the amount of time used. The space complexity measures the amount of space used. The best case, average case and worst case complexities are of interest. The asymptotic complexity when a problem becomes "large" is usually important and O( ) notation is used to quantify this. Logic is invaluable in program proof. 

The mathematics required for this analysis is summarised here. A mathematically able reader should skip this chapter. Other readers should scan it quickly and refer back to it when the material is needed in later sections. 

Recurrence Relations
Recurrence relations often arise in calculating the time and space complexity of algorithms. The amount of time (or space) that a program takes, Tk, is typically a function of the size, k, of the input data. A recurrence relation arises when Tk is some function of Tk' for k'real
Define f is O(g)
if there exist k and m such that
n>=m   =>   f(n) <= k*g(n)

Beyond m, f does not exceed k*g for some fixed k and m. Eg. 

x is O(3x)
x is O(x2)
0.01x2 is O(x2)
3x2+7x-8 is O(x2)

It can be seen that if m=m.
i.e. f grows no more rapidly than g, in the long run, give or take a multiplicative constant.


f is OMEGA(g) iff 
there are positive constants k and m s.t. f(n)>=k*g(n) for n>=m; equivalently g(n)<=(1/k)*f(n) so g is O(f).
i.e. f grows at least as quickly as g, in the long run, give or take a multiplicative constant.


f is THETA(g) iff 
f is O(g) and f is OMEGA(g), or equivalently f is O(g) and g is O(f).
i.e. f and g grow at the same rate, in the long run, give or take a multiplicative constant.


f is o(g) iff 
f is O(g) and f is not THETA(g).
i.e. f grows strictly more slowly than g, in the long run, give or take a multiplicative constant.


(OMEGA and THETA should be capital Greek letters, but HTML does not have them, yet.) 



Some Common Forms
The complexity of a single loop is usually obvious. 


for i :1..n
   body
end for

If the body of the loop always takes (approximately) the same amount of time to execute, regardless of i or n, the loop's overall complexity is O(n). Many programs on one-dimensional arrays have this form. See for example the earlier section on swapping array segments. Note that what appears to be a single loop may actually be a nested loop if the body calls a procedure or function that contains a loop. 

Nested loops often, but not always, have worse time complexity than a single loop. 


for i :1..m
   for j :1..n
      body
   end for
end for

Again provided that the time to execute the body is independent of i, j, m and n, the complexity is O(m*n). Many programs on two-dimensional arrays have this form. For example the dynamic-programming algorithm on strings A and B takes O(m*n) time where m=|A| and n=|B|. If the inner and outer loops are both executed from 1 to n, the complexity is O(n2). If the inner loop is executed i times the complexity is of the same order. 

for i :1..n
   for j :1..i  % same complexity for j :i..n
      body
   end for
end for

The body is executed 1+2+3+...+n = n*(n+1)/2 times which is still O(n2). 

Estimation of Complexity
Sometimes it is not easy to get a formula for the complexity of an algorithm. In such cases it may be possible to estimate it by experiment. Counting-variables can be added to the program, incremented when some critical operation is carried out and the final totals printed. The running time can also be measured, either by a stop-watch or better by calling a routine to print the computer system's clock. The complexity might be inferred by examining how such measures vary with the problem size. 

The accuracy of timing a program or an operation can be improved by timing a number of executions, perhaps in a loop, and dividing the total time taken by that number. A time-shared computer is used by many people simultaneously. The elapsed time taken by a program depends on the system load. Therefore any timing done on a shared machine must be based on the central processor time devoted to the particular program under study and not on the elapsed time. 

Examining differences between adjacent terms in a series can indicate the form of the underlying function that defines the series. A linear function, T(n)=a*n+b gives rise to constant difference between T(n) and T(n-1): 
D1(n) = T(n)-T(n-1) = a*n+b-a*(n-1)-b = a 
A quadratic function T(n)=a*n2+b*n+c gives rise to linear first-order differences: 
D1(n) = T(n)-T(n-1) = a*n2+b*n+c-a*(n-1)2-b*(n-1)-c = 2a*n-a+b 
which gives rise to constant second-order differences D2(n) = D1(n)-D1(n-1). In general, a polynomial of degree d is revealed by constant dth-order differences. 

Plotting graphs of measured quantities against the problem size is another useful technique. If the complexity has the form T(n) = a*nd for some order d then log(T(n)) = log(nd)+log(a) = d*log(n)+log(a). In this case a plot of log(T(n)) against log(n) should give a straight line with slope d. Log(1) is zero, so the line crosses n=1 at log(a). If T(n) is O(nd) the line and its slope may only be evident asymptotically for large n. A good range of values of n must be chosen. If T(n) = a*nd+b*ne where d>e and a is much smaller than b, T(n) may appear to be O(ne) from small values of n whereas it is really O(nd). 

If T(n) = an then log(T(n)) = log(an) = log(a)*n and a plot of log(T(n)) against n should give a straight line with slope log(a). 

Extra care must be taken if the behaviour of an algorithm depends not only on the size of the input but also on other characteristics of it. For example, some sorting algorithms examined later run faster or slower depending on the amount of ordering in the input. The results of a large number of runs on random data may have to be averaged to enable conclusions to be drawn. 

Logic and Boolean
The use of logic is indispensable in computer programming. It is essential to know that a program is correct. For this reason some programming languages provide forms to help in proving programs correct, e.g. 


assert 


if p then
   ...
else [not p must be true here]
   ...
end if


loop
[invariant ]
 ...
end loop


while p do
[invariant]                  % provided that
 body                        % [invariant] body [invariant]
end while
[invariant and not p]


procedure p
[pre  ]
[post ]
 ...
end p

These forms are used to include tests of conditions that are necessary to the correct functioning of a program. If a test fails, the system halts the program with an informative message rather than allowing the program to run amok. Most systems also have flags or switches that allow this checking to be turned off once confidence in the program has been established. When carefully chosen, the tests can also be used to prove that a program is correct. To do this it is necessary to prove that the program terminates and that it produces the correct results when it terminates. (If your programming language does not have `assert' etc. or equivalents, you can generally create your own with suitable procedures or macros.) 

The tests that can be included in a program are boolean expressions. 


Type:
   boolean

Constants:
   true, false

Operations:
   and, or, =>, =, not = :boolean2 -> boolean
   not :boolean -> boolean

Rules, p, q, r :boolean :
   p and q     = q and p                     % and
   true and p  = p
   false and p = false

   p or q     = q or p                       % or
   true or p  = true
   false or p = p

   p=>q = not p or q                         % implies

   not true  = false                         % not
   not false = true


   p and (q or r) = p and q or p and r       % distributive
   p or (q and r) = (p or q) and (p or r)    % laws


The Abstract Data Type Boolean.
Operators vary between programming languages. Note that these rules are mathematical ideals for a language to attempt to implement. A point of difference is that in some languages, e.g. Turing 

p and q    can be replaced by    q and p

only when both p and q always terminate correctly and evaluate to true or to false (and have no side-effects), similarly for `p && q' in C and its close relatives. For example 

x > 0 and 1/x > x

will return true or false for all values of x. But 

1/x > x and x > 0

is not defined when x is zero due to trying to divide one by zero. The former is making use of 

false and p = p    where p is  1/x > x

to avoid evaluating p. The fact that Turing and C, do this "short-cut" evaluation is often very convenient. A similar shortcut is taken for "true or p". Some languages, such as Pascal, do not take these short-cuts. 

Sometimes to prove a program it is necessary to use logical expressions that are not easily expressed as boolean expressions in the programming language. In such cases comments can be used. They are not checked automatically but they make very informative comments for another reader. 

(Also see the [Wff] pages for more on logic.) 

Exercises
Suppose that algorithm A takes 1000n3 steps and algorithm B takes 2n steps for a problem of size n. For what size of problem is algorithm A faster than B? 
What is the time complexity of the traditional manual integer multiplication method, i.e. `long multiplication', as a function of the length (not value) of the integers to be multiplied? 
What is the time complexity of the usual matrix multiplication algorithm if it is assumed that basic arithmetic operations on numbers take O(1) (constant) time? 
Insert a counting variable L in the inner loop of the dynamic programming algorithm for the edit distance. Do runs on pairs of strings of equal length `n' for various values of n. Plot log(L) against log(n). 
Below is a list of pairs of statements. For each pair, indicate if one statement is stronger than the other, ie. if one implies the other, or not. 
It's raining. It's pouring. 
N is a multiple of six. N is even. 
A lack of vitamin C causes scurvy. Eating vitamins makes you healthy. 
The animal is a marsupial. The animal is a kangaroo.