# teaching machines

## CS 240: Lecture 5 – Analysis Lab

September 3, 2021 by . Filed under cs3, fall-2021, lectures.

Dear students:

Today we will practice measuring or analysing algorithms in lab exercises. But first we need to muddy the waters just a bit more. What is cost function of this algorithm?

public static boolean contains(int target, int[] numbers) {
for (int number : numbers) {
if (number == target) {
return true;
}
}
return false;
}

The number of steps required really depends on what number we’re looking for and what numbers are in the array. How many comparisons might we need to make? In the best case we’ll find the element immediately. So, the cost would be 1 comparison. In the worst case, we’ll have to examine all elements, and the cost would be $n$ comparisons. In the average case, we can expect to examine half of the elements.

These different cases have very different complexity classes:

• $1 \in O(1)$
• $n \in O(n)$
• $\frac{n}{2} \in O(n)$

In general, computer scientists are most concerned with the worst case and average cases. In this class, we will mostly focus on the worst case.