public static boolean contains(int target, int[] numbers) {
for (int number : numbers) {
if (number == target) {
return true;
}
}
return false;
}
Basic Operation: number of key comparisons
Finding the average case:
Specify the distribution to average over (do we assume that the item is in the collection? 50% likely to be in the collection? In this case we will assume the key is in the array, and equally likely to be at any position.)
Sum over the cost of all possible outcomes, and divide by the number of outcomes.
public static boolean contains(int target, int[] numbers) {
for (int number : numbers) {
if (number == target) {
return true;
}
}
return false;
}
Basic Operation: number of key comparisons
Finding the average case:
Specify the distribution to average over (do we assume that the item is in the collection? 50% likely to be in the collection? In this case we will assume the key is in the array, and equally likely to be at any position.)
Sum over the cost of all possible outcomes, and divide by the number of outcomes.
For if and only if there exist positive constants |
For if and only if there exist positive constants |
For if and only if there exist positive constants |
For if and only if there exist positive constants |
|
In practice, people use big-O in several different ways:
Alyce is working on the analysis of a complex algorithm for finding sequence matches in a DNA database. She can easily show that the algorithm requires no more than
A)
B)
C)
D)
E)
What relationship(s) is(are) illustrated by the following figure?
A) |