Explain time complexity using an integration workload

Suppose an integration must match each incoming ID against known records. Repeated list scans grow with the number of records; an index changes the lookup work.

Count logical operations

The engineering foundations lab searches for the last of 100 keys.

from engineering_cases import complexity_case

result = complexity_case()
assert result["n"] == 100
assert result["linear_checks"] == 100
assert result["indexed_checks"] == 1
assert result["linear_class"] == "O(n)"
assert result["lookup_average_class"] == "O(1)"
assert result["timing_benchmark"] is False

Building the dictionary itself costs time and memory, so one lookup may not justify it. Repeated lookups often do. Big-O describes growth, not milliseconds; network and database latency may dominate the end-to-end service.

State input size, dominant operation, average/worst case and preprocessing. Use database indexes for durable queries and measure their write/storage trade-offs with query plans.

The FDE for Freshers course teaches complexity through API and data-pipeline workloads.

Exercise

Compare matching M events to N records with nested loops, a dictionary and a database index. Derive growth first, then benchmark representative sizes separately.

Continue learning

This article is part of the FDE engineering foundations sequence. Use the neighbouring tasks when you need the prerequisite or the next application.

• Review the prerequisite or neighbouring task in Choose a data structure for a practical engineering problem.
• Continue with Refactor a notebook into a tested service.

Reference: Python time-complexity reference.