Linear scans vs logarithmic hunts

Beginner Asymptotics & empirical timing

Created by Pavel · 29.04.2026 at 19:08 UTC

Searching for a value in an unsorted Python list requires a linear scan in the worst case—you might inspect every element. If you can sort once and answer many queries, binary search (bisect) gives O(log n) per query after the O(n log n) sort. If you only need membership and not order, a hash set gives expected O(1) lookups at memory cost.

These trade-offs drive real pipelines: feature dictionaries keyed by string IDs, deduplication with sets, quantile thresholds on sorted arrays, and database indexes (B-trees) behind ORMs.

Choose the structure that matches your access pattern: one-off scan, many queries on static sorted data, or many membership tests with no ordering requirement.

bisect module: [1].

Sources

[1]https://docs.python.org/3/library/bisect.html Return to text

University approvals: 0

Tasks

Question 1

Worst-case comparisons to find a value in an unsorted list of length n (no extra structure) are:

Hint

Adversary hides the target in the last slot.

O(1)

O(log n)

O(n)

O(n log n)

Question 2

You load a static sorted array of thresholds and will issue 10⁶ queries for different scalar values. After an initial sort (already given), each query should be:

Hint

Sorted order enables halving.

O(n) scan every time

O(log n) bisection

O(n²)

O(1) without extra memory

Question 3

lin_search(vals, target) returns the first index of target in vals or None. Single forward pass.

Hint

Linear scan with early exit.

def lin_search(vals, target):
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

2 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Asymptotics & empirical timing
Difficulty: Beginner
Completed: 0 users

Creator

Pavel