Best and worst case
- Algorithms course
- Beginner
- Lesson 15/80
- 4 min
Best case O(1), worst case O(n) for linear search.
Best and worst case
In linear search, the best case: target is first, 1 comparison, O(1). The worst case: target is last or absent, n comparisons, O(n).
Average case: target is in the middle, n/2 comparisons. Since Big-O ignores constants, the average is also written O(n).
Sorted vs unsorted array
Linear search does not require the array to be sorted. In sorted arrays, the search can stop when an element larger than the target is seen.
However, this optimization does not change the worst case: if the target is absent, the whole array is still scanned and complexity remains O(n).
Practice Contains
Write contains(arr, target). Return True if found, False otherwise. Print True with print(contains([1, 3, 5], 3)).
Starter code
def contains(arr, target):
# Check if existsSample solution
def contains(arr, target):
# Check if exists
for x in arr:
if x == target:
return True
return False
print(contains([1, 3, 5], 3))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Best and worst case: match the terms
| Term | Meaning |
|---|---|
Best |
1 comparison |
Worst |
n comparisons |
Average |
n/2 comparisons |
Not found |
returns -1 |
2 How many comparisons does the average case make?
- n Correct answer
- n/2
- 1
- n^2
Explanation: The average case makes n/2 comparisons.
3 Best case
If the target is first, ____ comparison is made.If the target is first, 1 comparison is made.Explanation: 1 is right.