Computational Complexity

There are three parts to this practical. Task 1 provides a set of exercises to practice your understanding of summation. You should be be able to do these. If you cannot, revise the content of the lecture. Task 2 asks you to look at a number of algorithms and estimate the time complexity of each.

Finally, the challenge formally defines an algorithm using a Turing machine and asks you to derive and prove its time complexity. This is optional but recommended if you are interested in deepening your understanding of computational complexity.

Mathematics and Problem Solving

5. Computational Complexity

David Gundry

Student Voice Survey

Please complete the Student Voice survey for this module

Your responses are important for improving the module, especially written responses

You can also find the link on Moodle

Task 1.1: Calculate summations

In the following question, instead of working by hand, you might wish to write a script to compute these for you using a for loop. (Depending on your experience with programming, you may also be able to write a generic summation function that calculates a summation for any lower and upper bound of $i$ and an arbitrary formula $f(i)$ passed as a callback or function pointer)

For some of these you may recall a formula from the slides that will make calculation easier.

Calculate the following summations.

$ \sum_{i=1}^{10} 1 $
$ 10 $
$ \sum_{i=1}^{10} i $
$ 55 $
$ \sum_{i=1}^{5} a $
$ 5a $
$ \sum_{i=1}^{10} i^2 $
the sum of the first 20 natural numbers
$ \frac{n(n+1)}{2} $; where $ n = 20 $
$ \frac{(20(20+1))}{2} = 210 $
the sum of the first 20 square numbers
$ \frac{n(n+1)(2n+1)}{6} $; where $ n = 20 $
$ \frac{20(20+1)(2(20)+1))}{6} $
$ = \frac{20 \times 21 \times 41}{6} $
$ = \frac{17220}{6} = 2870 $
$ \sum_{i=1}^{n} 2 $
$ 2n $
$ \sum_{i=1}^{n} a $
$ an $
$ \sum_{i=4}^{n} 10 $
$ 10(n-3) $
$ \sum_{i=0}^{n-1} (a + 4) $
$ n(a+4) $
$ \sum_{i=-5}^{n+3} 13k^n $

Task 1.2 Simplify summations

To be able to calculate time functions it is necessary to be able to simplify summations.

Simplify the following summations.

$ \sum_{i=1}^{n} 3ci $
$ \sum_{i=1}^{n} (3i + 4) $
$ \sum_{i=1}^{n} (2i^2 + 3i) $

Product Exercises

Product notation works similarly to summation notation. However instead of adding the elements together, they are multiplied together

\[ \prod_{k=1}^4 (k+1) = (1+1) \times (2+1) \times (3+1) \times (4+1) = 120 \]

Compute the following products:

$ \prod_{k=1}^4 2 $
$ \prod_{k=1}^4 k $
$ \prod_{k=1}^3 \frac{k}{k+1} $
$ \prod_{k=0}^7 2^k $; with this question remember that $ x^a + x^b = x^{a+b} $

Task 2: Time complexity examples

For each of the algorithms given below, take a guess at its time complexity. These are not all quite as straightforward as the above examples. Remember it is only the rate of increase of the time function that we care about, so we can make some significant approximations for simplification. For example, if we want to work out the worst case time complexity, we might assume all conditional tests fall out in a way such that we do the most work.

There is a useful rule of thumb that you should use. A list of instructions that take constant time with no loops will be $O(1)$. If there is a loop over something $n$-like (e.g. $1\rightarrow n$, $0\rightarrow (n-1)$, or $0\rightarrow 2n$), the time complexity will be $O(n)$. If this loop is itself in another loop over something $n$-like, the time complexity will be $O(n^2)$. For every nested loop the power of $n$ will increase by 1. Three nested loops over $n$ would be $O(n^3)$ and so on.

This is only a rule of thumb and not a substitute for formal proof, but it can help you in many if not most cases, and is sufficient for this question.

Function Power(a: N, p: N)
    x := 1
    for i := 1 to p
        x := x * a
    endfor
    return x

Function StringEquals(A: string, B: string)
    if length(A) != length(B) then
        return false
    for i := 0 to length(A)-1
        if (A[i] != B[i])
            return false
    endfor
    return true

Procedure InsertionSort(A : list of sortable items)
    for i:= 1 to length(A)-1
        j := i
        while j > 0 and A[j-1] > A[j]
            swap A[j] and A[j-1]
            j := j - 1
        end while
    end while

Procedure BubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n-1 do
            if A[i-1] > A[i] then
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped

Challenge 1: Algorithm analysis

An algorithm that checks whether an input string is a palindrome with an even number of symbols (e.g. 00, 0110, 010010) is formalised in the Turing machine below.

Your challenge is to work out the worst-case time complexity of this algorithm by deriving the time function. This function takes as input the length of the string provided to the Turing machine and returns the number of steps reported by the Turing machine when it halts ("time taken"). Having derived this function you can then identify the complexity class of this algorithm.

As a simplification, consider only inputs that are palindrome strings with an even number of characters (i.e. inputs the machine will accept). If you wish you may satisfy yourself that the Turing machine will always reject an incorrect input in fewer steps it will accept a correct one. Thus our time function will give us the worst case running time.

There is advice to help get you started below.

Turing Machine Rules
Starting state		Input tape:
State	Input	Write	Go to	Move

Turing Machine
Read head
Tape	0	1	0	0	1	0
Current state	Start
Time taken	0

Getting Started

A good place to start is to begin gathering some data. You will not need this data in deriving the time function, but it will be necessary later to allow you to check whether your answer is correct. Complete and extend the following table. You may wish to do this in a spreadsheet so you can produce a graph of $T(n)$.

This table shows the time taken (in steps) for the Turing machine above to halt on palindrome inputs of length $n$.

n	2	4	6	8	...
T(n)	6	15	...	...	...

At this point you can rapidly get an approximate sense of how the function will grow, and you may be able to take a good guess already at what the time complexity is. However, we want to be able to prove we are correct.

Counting rule

To come up with a time function, we need to determine a rule that lets us count how many steps the Turing machine takes for our algorithm. You might begin by writing down a list of operations for an input of length $n$. You could extend the table below. Here I have only included the movement of the read head because that is sufficient for us to work out the rule in this case.

Operation	Repeat
Move right	n
Move left	1
Move left	n-1
...	...

As we do so often, we need to look for patterns. We want to be able to express the number of steps using summation as a function of $n$.

Once you have a counting rule expressed as a summation (a time function). Simplify it to identify the fastest-growing term. Also, double check it against the data you collected earlier to make sure you haven't made a mistake.

Question

Answer this question once you have found and checked your answer for the time complexity of this algorithm.

Do you think another algorithm could solve the same problem with a smaller time complexity? Consider both algorithms that run on Turing machines of the kind above as well as algorithms that you could describe in pseudocode that could be implemented in a programming language such as Python.

What is it about the Turing machine that makes checking palindromes slower? What changes to a Turing machine (e.g. additional tapes, different movement rules, the addition of new types of operation) would allow it to compute this algorithm in fewer steps?

Challenge 2: Two-Tape Turing Machine

So far we have talked about one-tape turing machines. These are Turing Machines that operate on a single tape with a single read head. However, there is nothing stopping us from devising other kinds of abstract machine based on the Turing Machine. One such is a Two-Tape Turing Machine, which is distinguished by having two tapes. This is a type of Multitape Turing Machine.

Imagine you had a turing machine but instead of one tape and read head, it has two tapes each with their own read head. The machine would be able to act differently based on the symbol that each of the read heads is currently reading. It would be able to move each head independantly. The input is provided on tape 1, with the second tape intially being blank. The machine still is only in one state at a time.

Part 1: Describing the machine

What would the rules look like for a Two-Tape Turing Machine? Compare to the rules given above for a single tape Turing Machine. What additional information does each rule need to contain? What additional inputs does the rule need to have? What additional outputs does the rule need to have?

Write a minimal program example for a Two-Tape Turing Machine just to demonstrate the rules.

You have already been analysing the program for identifying palindromes on a one-tape machine. Hopefully you now have a good understanding of what is involved in detecting a palindrome. Now that we have a two-tape machine, let's see if we can produce a more efficient program that makes use of the second tape.

Part 2: Palindromes

Implement a program to check whether a string is a palindrome on the Two-Tape Turing Machine. You will need to write a list of rules in the format you worked out above, as well as identifying the initial state and a halting state. As there is not interactive tool to check these for you, you will have to reason about how these rules will behave to convince yourself that you have the right answer.

Test your rules manually using paper and pencil for a short palindrome string.

While you can implement an identical program to the one given above for a one-tape Turing Machine, by making use of the second tape, it is possible to implement an algorithm that is significantly more efficient.

You should now have two algorithms to determine whether a string is a palindrome. One works on a one-tape turing machine, and the other works on a two-tape turing machine. Hopefully you have been able to find an algorithm for the two-tape turing machine that is more efficient.

Part 3: Comparing Complexity

You have already calculated the computational complexity of the algoritm for the one-tape Turing Machine in Challege 1 above. You shold now be able to calcualate the computational complexity of the algorithm for the two-tape turing machine.

You will hopefully have been able to find that the Two-Tape Turing Machine is able to detect palindromes more time-efficiently than if it had only one tape.

Part 4: Extra Challenge: Simulating the Two-Tape Turing Machine

Any algorithm that can be implemented on a Two-Tape Turing Machine can also be implemented (although possibly slower) on a One-Tape Turing Machine.

Can you prove this?

Think about how you could simulate a Two-Tape turing machine on a one-tape turing machine. Demonstate the principle behind your idea with a small example program

You will need to decide how to combine the two tapes into one tape. You will need to decide how to translate the application of a single rule step in a two-tape machine to (possibly multiple) steps of a one-tape machine.