1. Demonstrate the following statements:

  1. log 3n2 is O(log n)

  2. 2n+1 log n2 is O(2n log n)

  3. n! is O(nn)

  4. 2n is O(22n)

  5. 22n is not O(2n)

  6. 6n2-2n+7 is O(n3+n2)

  7. n3+n2 is not O(6n2-2n+7)

Recall that: log na = a log n and abn = (a n)b.

2. Prove the following statements:

  1. f1(n)+f2(n) is O(g1(n)+g2(n)) if f1(n) is O(g1(n)) and f2(n) is O(g2(n))

  2. f(n) is O(g(n)) iff g(n) is &Omega(f(n))
3. Given the following Matrix class definition: 

public class Matrix {
  private int noRows;
  private int noCols;
  private int[][] m;

  public Matrix(int r, int c) {
    if (r <= 0 || c <= 0)
      throw new RuntimeException("Dimensions...");
    noRows = r;
    noCols = c;
    m = new int[noRows][noCols];
  }

  public int getNoRows() {return noRows;}
  public int getNoCols() {return noCols;}

  public void set(int r, int c, int value) {
    if (r > noRows || r <= 0 || c > noCols || c <= 0)
      throw new RuntimeException("Index...");
    m[r-1][c-1] = value;
  }

  public int get(int r, int c) {
    if (r > noRows || r <= 0 || c > noCols || c <= 0)
      throw new RuntimeException("Index...");
    return m[r-1][c-1];
  }

  public static Matrix transpose(Matrix m) {
    Matrix r = new Matrix(m.getNoCols(), m.getNoRows());
    for (int i = 1; i <= m.getNoRows(); i++)
      for (int j = 1; j <= m.getNoCols(); j++) {
        r.set(j, i, m.get(i, j));
      }
    return r;
  }

  public static Matrix transposeSquare(Matrix m) {
    if (m.getNoRows() != m.getNoCols())
      throw new RuntimeException("Matrix is not square.");
    Matrix r = new Matrix(m.getNoRows(), m.getNoRows());
    for (int i = 1; i <= m.getNoRows()-1; i++)
      for (int j = i; j <= m.getNoRows(); j++) {
        r.set(i, j, m.get(j, i));
        r.set(j, i, m.get(i, j));
      }
    return r;
  }
}

  1. What is the complexity of the transpose method?

  2. What is the complexity of the transposeSquare method?
4. The binarySearch method below can be used to determine if a target element appears in a sorted array arr of integers. 

public static boolean binarySearch(int[] arr, int target) {
  int l = 0;
  int u = arr.length-1;
  int m;

  while (true) {
    m = (l + u) / 2;
    if (target == arr[m])
      return true;
    else if (target < arr[m])
      u = m-1;
    else
      l = m+1;
    if (l > u)
      return false;
  }
}

What is the complexity of the binarySearch method?

5. The hanoi method below solves the 3-peg Towers of Hanoi problem. 

public static void move(int r, int s) {
  System.out.println("Move disk from pole " + r + " to pole " + s);
}

public static void solve(int n, int r, int s) {
  if (n == 1) {
    move(r, s);
  }
  else {
    solve(n-1, r, 6-r-s);
    move(r, s);
    solve(n-1, 6-r-s, s);
  }
}

public static void hanoi(int n) {
  solve(n, 1, 3);
}

What is the complexity of the hanoi method in terms of the number of calls made to the move method?

6. Topic 8 of the lecture notes calculated a closed form equation for the complexity of the recursive multiply method of the RMaths class introduced in Topic 3.
  1. Use the same technique to determine a closed form equation for the complexity of the (different) multiply method below: 

    public static int increment(int i) {return i + 1;}
public static int decrement(int i) {return i - 1;}

public static int add(int x, int y) {
  if (y == 0) return x;
  else return add(increment(x), decrement(y));
}

public static int multiply(int x, int y) {
  if (y == 0) return 0;
  else return add(multiply(x, decrement(y)), x);
}

  2. Determine a closed form equation for the complexity of the recursive power method below: 

    public static int power(int x, int y) {
  if (y == 0) return 1;
  else return multiply(x, power(x, decrement(y)));
}

    Use the definitions of multiply and decrement from Exercise 6a.