Exercise II

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 $n$?

A) $O(n)$
B) $O(\lg n)$
C) $O(n^2)$

Solution

The correct answer is $O(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 $n$. In the Big-Oh notation, we suppress the constant factors.

Reminder: we are considering the worst-case scenario.