Best and worst case

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).

Exercise Contains

Write contains(arr, target). Return True if found, False otherwise. Print True with print(contains([1, 3, 5], 3)).

Show example 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))

Test yourself

Best and worst case: match the terms

Best

1 comparison
Worst

n comparisons
Average

n/2 comparisons
Not found

returns -1
How many comparisons does the average case make?
- n
- n/2
- 1
- n^2
Show answer

n — The average case makes n/2 comparisons.

Best case

If the target is first, ____ comparison is made.

Show answer

If the target is first, 1 comparison is made.

Next lesson: Summary - Linear search

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies