First, the key terms.

Input size
The amount of data the algorithm processes, often denoted n.
Big-O
A description of an upper-bound growth class, not an exact stopwatch measurement.

The idea, explained

Big-O notation expresses an upper-bound growth class while abstracting away some constants and lower-order terms. It is useful for comparing scaling behavior, not predicting exact runtime on a device. A linear scan examines up to every item; binary search repeatedly halves a sorted search range. Data preparation, memory use and network operations can change the best practical choice. Measure realistic workloads as well as reasoning about complexity.

STEP 1

Start with a simple scan

To find a name in an unsorted list, compare names one at a time. If the desired name is last or absent, every entry must be checked. Doubling the list roughly doubles the number of comparisons in that worst-case procedure.

STEP 2

Use ordering to eliminate work

In a sorted list, compare with the middle entry. If the target is earlier alphabetically, discard the later half. Repeat on the remaining half. The search works because ordering tells you where the target cannot be.

STEP 3

Include preparation and real costs

Sorting the list is work, and maintaining its order after updates can also cost time. If you only search once, sorting solely for that search may not pay off. If you search repeatedly, an ordered structure may be worthwhile. Hardware, storage and network delays still matter.

Follow a worked example.

Searching 1,024 sorted catalogue IDs by halving the search range takes about ten comparisons in a simplified binary-search example. A scan may examine all 1,024 IDs. Sorting the catalogue in the first place also has a cost.

Walk it through, one step at a time

  1. Search sorted IDs 1 through 16 for ID 14. A middle comparison around 8 eliminates the lower half.
  2. A comparison around 12 narrows the range again. A later comparison reaches 14. The exact sequence depends on midpoint conventions.
  3. Compare this with scanning from 1, which needs 14 comparisons to reach 14. Now ask how often the list changes before choosing a structure.

Where people get stuck

An algorithm with a better asymptotic class can still be slower for small inputs or costly storage access.

Now try it yourself.

Pause before opening each answer. Explain your reasoning in your own words.

1. Check the core idea

What condition makes ordinary binary search valid?

Reveal the answer & reasoning

The search range must be ordered consistently with the comparison used. Applying the same procedure to unsorted data can miss an existing item.

2. Apply what you learned

Why can a good theoretical algorithm still be a poor practical choice?

Reveal the answer & reasoning

Its setup costs, memory requirements or access pattern may dominate the actual workload. Complexity guides reasoning; realistic measurement checks the implementation.