Exercise II

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

Consider the following program

public boolean contains (int[] arr, int target) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
      return true;
    }
  }
  return false; 
}

Exercise What is the asymptotic running time of the code above for searching one array, as a function of the array length nn?

A) O(n)\Omicron(n)
B) O(lg⁡n)\Omicron(\lg n)
C) O(n2)\Omicron(n^2)

Solution

The correct answer is O(n)\Omicron(n). The key observation is that the code performs a constant number of operations for each array entry. Here "constant" means some number independent of nn. In the Big-Oh notation, we suppress the constant factors.

Reminder: we are considering the worst-case scenario.