Chapter 8 Algorithms and Algorithmic complexity
8.1 Algorithmic Complexity
Algorithmic complexity is a measure of how complicated a procedure is by counting roughly how many operations are required to complete it.
8.1.1 Big and little O notation
When we are talking about complexity (and in lots of other situations later in your degree) we are often only interested in the asymptotic behaviour of a function.
For example if we want to know the complexity of an algorithm to multiply two numbers with at most \(n\) digits together we have a function of \(n\) and we are only really interested in describing how it behaves when \(n\) is very large. Big and little O notation is a way of doing this.
Definition 8.1 (Big O) Suppose \(f(n)\) and \(g(n)\) are function of \(n\) and there exist real numbers \(C, n_0\) such that for \(n \geq n_0\) then \[|f(n)| \leq C g(n)\] then we say \[ f(n) = O(g(n)). \]
This is most commonly used when \(g(n)\) is a simple function like \(n^k\) for some \(k\) or \(\log(n)\) or \(a^n\) or something similar.
- Example 8.1
The function \(2n^3 + 3n - 102 = O(n^3)\).
\(\phi(n) = O(n)\) since \(\phi(n) \leq n\).
While we are defining big O notation it is useful to define little o notation
Definition 8.2 (little o notation) If \(f(n), g(n)\) are functions and for every \(c >0\) there exists \(n_c\) such that if \(n >n_c\) then \[ |f(n)| \leq c g(n),\] then we say \(f(n) = o(g(n))\).
We can think of this as saying \(f(n)\) becomes insignificant compared to \(g(n)\) as \(n\) becomes large.
Example 8.2 We have \(n^2 = o(n^3)\).
8.2 Running times of algorithms
We use big O notation to talk about how long it will take to run an algorithm as the input becomes large. It is easiest to understand this by looking at some examples.
Example 8.3 (Addition) Suppose we are adding two \(n\) digit numbers \(a_1\dots a_n\) and \(b_1\dots b_n\) using our standard method of addition where we do \(a_n+b_n\) and enter the unit part of this as the unit part of the sum then possibly carry the 1 if \(a_n + b_n \geq 10\). Then we add \(a_{n-1} + b_{n-1}\) and possibly add the additional \(1\) we carried if necessary.
If we want to count the steps it depends on precisely what we list as a step. If we only think we are doing 1 step when adding and carrying for each place value then we are performing \(n\) steps. If we think of each addition and carrying step as a separate step then we do \(3n\) steps. However in either case we say the algorithm is \(O(n)\).
Example 8.4 (Multiplication) Now suppose we think about multiplication using the long multiplication algorithm then for two \(n\) digit numbers we need to multiply \(a_k\) by \(b_j\) for each \(k, j\) (which is \(n^2\) steps) and then perform \(n^2\) addition steps of what are effectively at most two digit numbers. So this algorithm is O(n^2).
There are multiplication algorithms that are much faster but they are all worse than \(O(n)\).
Example 8.5 (Checking divisibility) Division is no worse than multiplication. The algorithms are a bit more complicated to state. In general division algorithms are also \(O(n^2)\).
If we want to see whether an \(n\) digit number is divisible by an \(m\) digit number then we can do this by repeated subtraction of the \(m\) digit numbers and multiples of it by \(10\). Each subtraction step is \(O(m)\) and we need to do at most \(O(n)\) of them so the algorithm is \(O(n^2)\).
We can also divide one number by the other and get some truncated decimal expansion by using Newton’s method which you may have learnt at school.
Example 8.6 (Naive primality testing) Suppose we want to test whether a number \(n\) is prime. The most obvious way to do this is to check whether we can find any other \(m \neq n\) such that \(m|n\). We notice here that we only need to check \(m \leq \sqrt{n}\) as if \(ab=n\) then one of \(a, b\) must be smaller than \(sqrt{n}\). If we suppose it is one step to check whether \(n\) is divisible by \(m\). Now each division operation is a check and the number of digits in \(n\) is around \(\log_{10}(n)\) so if we are interested in testing an \(N\) digit number to see if its prime we need around \(10^{N/2}N^2\) operations so the algorithm is \(O(10^{N/2} N^2)\).
Remark. Notice in all of these examples we are using our understanding of the complexity of less complicated operations to find the complexity of more complicated operations.
Definition 8.3 (Fibonacci Numbers) The Fibonacci numbers are defined by \[ f(k+2) = f(k+1 ) + f(k), \] and \(f(0)=f(1)=1\).
We discover that if we want to count how many steps Euclid’s algorithm takes then the Fibonacci numbers appear.
Theorem 8.1 (Complexity of Euclid's Algorithm) If \(a>b\) and Euclid’s algorithm takes \(k\) steps to complete then \(a \geq f(k+2)\) and \(b \geq f(k+1)\).
Proof. We prove this by induction on \(k\).
In the base case if the algorithm takes \(1\) step then we must have \(b\geq 1=f(2)\) and \(a>b\) so \(a \geq 2 = f(3)\).
Now we assume it is true for \(k-1\) steps. Then suppose we have \(a,b\) which need \(k\) steps for Euclid’s algorithm. Then \(a=qb +r\) and \(b,r\) need \(k-1\) steps for Euclid’s algorithm. So by our induction hypothesis we know that \(b\geq f(k+1), r \geq f(k)\). Then \(a = qb +r \geq b +r \geq f(k) + f(k+1) = f(k+2)\).
Remark. The above theorem means that the Fibonacci numbers represent the worst case for Euclid’s algorithm. i.e. \(f(k+2), f(k+1)\) are the smallest numbers that will need \(k\) steps to complete Euclid’s algorithm for.
We can show that for \(k\) large \(f(k) \approx \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^k\) so \(k \approx \log(f(k))/\log((1+\sqrt{5})/2)\). Therfore the complexity of Euclid’s algorithm when the larger number is \(n\) is \(O(\log(n))\).
Definition 8.4 (polynomial time) We say that an algorithm takes polynomial time if the complexity is \(O(n^k)\) for some \(k\) (in the input size \(n\)).
Remark. Problems where there is no known polynomial time algorithm are considered very hard for computers to do. These provide a good oportunity for creating codes and encryptions which are hard to break.