CS 240: Lecture 5 – Analysis Lab
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.
Ask lots of questions.
TODO
- Take the mastery quiz on Canvas before the end of Sunday.
- Read 6.09-6.10 and 6.12-6.13 in OpenDSA.
- Keep working on PA1. Run into issues now, while there’s time to address them.
See you next time.
