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

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

Solution

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

Reminder: we are considering the worst-case scenario.