Hand-in

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 ratio) the algorithm will take when the input size is a) 101, b) 200, c) 10000, and finally d) assuming that $T(n)$ is the runtime measured in seconds, what is the biggest problem it can solve within 100000 seconds (a day and a bit)? One of the answers is already filled in to help you start.

1. $T(n) = \log_2 n$
2. $T(n) = n$
3. $T(n) = n \log_2 n$
   
   answer:
   
   $T(100) = 100 \log_2 100 ≈ 664$
   $T(101) = 101 \log_2 101 ≈ 672 ≈ 1.012 × T(100)$
   $T(200) = 200 \log_2 200 ≈ 1529 ≈ 2.3 × T(100)$
   $T(10000) = 10000 \log_2 10000 = 10000 × 2 \log_2 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 \log_2 n$. We cannot solve this symbolically but the solution is $n ≈ 7740.96$. Since $n$ must be a whole number, the answer is 7740.
4. $T(n) = n^2$
5. $T(n) = n^3$
6. $T(n) = 2^n$

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. ex2 is solved for you already. For ex6 to ex10 you should write a recurrence relation for $T(n)$ which may use Big-Oh notation. You should then write down the complexity of each function.

You may assume that n is a power of two if it helps.

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;
}

Answer:

• Outer loop runs n times.
• For each value of i, inner loop runs n-1 times (from 1 to n-1).
• Total is: $n(n-1)$, $O(n^2)$.

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);
}