Exercise VII

  • Use Big-Oh notation to describe the asymptotic runtime of a program.

Consider the following program

public int indexOf (String str, char target) {
  for (int i = 0; i < str.length; i++) {
    if (str.charAt(i) == target) {
      return i;
    }
  }
  return NOT_FOUND; 
}

We have counted the number of steps indexOf takes to execute and expressed it as a function T(N)T(N) where NN is the size of the input String (str).

ScenarioExact running timeAsymptotic running time
Best-caseT(N)=4T(N) = 4
Worst-caseT(N)=4N+3T(N) = 4N + 3

Exercise Complete the table above. Use Big-Oh for expressing asymptotic running time.

Solution
ScenarioExact running timeAsymptotic running time
Best-caseT(N)=4T(N) = 4O(1)\Omicron(1)
Worst-caseT(N)=4N+3T(N) = 4N + 3O(N)\Omicron(N)

The O(1)\Omicron(1) represents the running time that does not depend on the input size. However, it does not mean it only takes one step!