Learning Goals

• To understand Big-Oh notation
• To compute the running times of simple methods

Exercise: Complexity and running times!

This exercise involves NO programming.

Study the following mystery methods. For each, describe the running time in terms of the variable n. Feel free to include a big-O expression. Then, in a couple of sentences, explain your answer. For example, it would be better to say "That loop will run 2*n + 1 times" instead of "That loop will run O(n) times". Try to give a concise and thorough explanation. For example, if a loop runs 2*n times, make sure to explain where the 2 and the n come from.

Task 1

private int mystery(int n) { 
  int sum = 1;
  for (int i = 0; i < n; i++){ 
     sum = sum*2;
  }
  for (int i = 0; i < n; i++){ 
    for (int j = n; j > 0; j=j/2) {
      sum = sum + n; 
    }
  } 
  return sum;
}

Task 2

public int mysterious(int n, int sum) { 
  int i = 0;
  while (i < n) { 
    i = i + 1;
    for (int k = 0; k < 25; k++) {
      sum = sum + i; 
    }
  }
  return sum;
}

Submit one PDF file, named ComplexityOnPaper.pdf that contains your answers to all questions, clearly marked: "Task 1 Answer" and "Task 2 Answer".

Make sure the document you submit contains your name. We will not grade submissions that do not include a name.

Good luck!