Exercise III

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

Consider the following program

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

Exercise What is the asymptotic running time of the code above for searching two arrays, as a function of the array lengths nn?

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

Solution

The answer is the same as before, O(n)\Omicron(n). The reason is that the worst-case number of operations performed (in an unsuccessful search) is twice that of the program in the previous exercise. This extra factor of 2 contributes only to the leading constant in the running time, and it will be suppressed in Big-Oh notation.