Deadlines: first deadline 29th April, final deadline 13th May. Submissions by Fire, in plain text, PDF or HTML format.

The purpose of this hand-in is for you to get a better idea of what the performance of different complexity classes is (part 1) and some practice calculating complexities of different functions (part 2).

Part 1

In this part you are given the runtime T(n) of several hypothetical algorithms. The algorithm takes a certain amount of time for an input of size 100. Calculate how much longer the algorithm will take when the input size is a) 101, b) 200, c) 10000. Finally, d) if the algorithm takes one second on inputs of size 1, what is the biggest problem it can solve in 100000 seconds (a day and a bit)? One of the answers is already filled in to help you start.

  1. T(n) = log2 n

  2. T(n) = n

  3. T(n) = n log2 n

    T(100) = 100 log2 100 ≈ 664.

    T(101) = 101 log2 101 ≈ 672 ≈ 1.012 × T(100).

    T(200) = 200 log2 200 ≈ 1529 ≈ 2.3 × T(100).

    T(10000) = 10000 log2 10000 = 10000 × 2 log2 100 = 200 × T(100).

    So: a) about 1.2% longer, b) about 2.3 times as long, c) 200 times as long.

    For d), we need to solve 100000 = n log2 n. We cannot solve this symbolically
    [Except using the Lambert W function.]
     but the solution is n ≈ 7740.96. Since n must be a whole number, the answer is 7740.

  4. T(n) = n2

  5. T(n) = n3

  6. T(n) = 2n

Part 2

In this part you will calculate the complexities of ten functions. Although they are toy functions, the techniques you use are just the same as for realistic functions.

For ex1 to ex5, you should first write down a mathematical function T(n) that counts exactly how many times the line sum += 1 is executed. You may assume that n is a power of two if it helps. For ex6 to ex10 you should write a recurrence relation for T(n) which may use big-O notation.

You should then write down the complexity of each function.

int ex1(int n) {
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += 1;
  return sum;
}
int ex2(int n) {
  int sum = 0;
  for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j++)
       sum += 1;
  return sum;
}
int ex3(int n) {
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += 1;
  for (int j = 1; j < n; j++)
    sum += 1;
  return sum;
}
int ex4(int n) {
  int sum = 0;
  for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < n*n; j++)
       sum += 1;
  return sum;
}
int ex5(int n) {
  int sum = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
      sum += 1;
  for (int k = 0; k < n; k++)
    sum += 1;
  return sum;
}
int ex6(int n) {
  if (n > 0)
    return 1 + ex6(n-1);
  else
    return 0;
}
int ex7(int n) {
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += 1;
  if (n > 0)
    return sum + ex7(n-1);
  else
    return 0;
}
int ex8(int n) {
  if (n > 1)
    return 1 + ex8(n/2);
  else
    return 0;
}
int ex9(int n) {
  int sum = 0;

  for (int i = 0; i < n; i++)
    sum += 1;

  if (n > 1)
    return sum + ex9(n/2);
  else
    return 0;
}
int ex10(int n) {
  if (n == 0)
    return 0;
  else
    return ex10(n-1) + ex10(n-1);
}