Algorithms
Describe an algorithm's behavior and rough growth before optimizing it.
On this page
The concept
An algorithm is a defined sequence of steps that solves a problem. Linear search inspects items one by one and stops at the first match. Its worst-case work grows with the number of items, written O(n). Set membership is typically O(1) on average, but constructing the set also costs time and memory.
Big-O describes growth, not a precise stopwatch result. A straightforward list search may be best for a tiny one-time query; a set may be better for many membership checks. First preserve correctness and clarity, then measure the workload that actually matters.
Worked example
def linear_search(items, target):
for index, item in enumerate(items):
if item == target:
return index
return None
numbers = [7, 3, 9, 2]
position = linear_search(numbers, 9)
if position is not None:
print("Found at:", position)
print(linear_search(numbers, 100))
unique_numbers = set(numbers)
print(9 in unique_numbers)Trace the result
- linear_search returns the first matching index.
- The caller checks is not None because index 0 would also be a valid result.
- The final set example answers membership but does not preserve the same index-search contract.
Found at: 2
None
TrueLine-by-line walkthrough
Lines 1–5: def linear_search(items, target):
Define the function linear_search with input names items, target. Definition stores the operation rather than executing its body. An ordinary call executes a normal function; a coroutine runs when awaited/scheduled, and a generator advances when consumed. Decorators can provide a context-manager or wrapper interface. Indented statements below belong to this operation.
Lines 2–4: for index, item in enumerate(items):
Obtain each item from enumerate(items) and bind it to (index, item) before executing the body. A tuple-shaped target unpacks that item. A loop else, if present, runs only when completion does not use break.
Lines 3–4: if item == target:
Evaluate item == target. Execute the indented body if it is truthy; otherwise follow the alternative branch, if present. Branch order and indentation are part of the behavior.
Line 4: return index
Evaluate index and return that value to the caller. This ends the current function call; subsequent statements on this execution path do not run.
Line 5: return None
Evaluate None and return that value to the caller. This ends the current function call; subsequent statements on this execution path do not run.
Line 8: numbers = [7, 3, 9, 2]
Evaluate [7, 3, 9, 2], then bind or update numbers with the result. The chosen collection determines how later access, membership, and mutation behave. Assignment itself does not imply a deep copy.
Line 9: position = linear_search(numbers, 9)
Evaluate linear_search(numbers, 9), then bind or update position with the result. The call finishes before its return value is bound; a failed call does not produce a successful assignment. Assignment itself does not imply a deep copy.
Lines 10–11: if position is not None:
Evaluate position is not None. Execute the indented body if it is truthy; otherwise follow the alternative branch, if present. Branch order and indentation are part of the behavior.
Line 11: print("Found at:", position)
Evaluate the print arguments from the current state and display them. sep controls separators and end controls the ending when those options are provided. Displaying a value does not return that value from the surrounding function.
Line 12: print(linear_search(numbers, 100))
Evaluate the print arguments from the current state and display them. sep controls separators and end controls the ending when those options are provided. Displaying a value does not return that value from the surrounding function.
Line 13: unique_numbers = set(numbers)
Evaluate set(numbers), then bind or update unique_numbers with the result. The call finishes before its return value is bound; a failed call does not produce a successful assignment. Assignment itself does not imply a deep copy.
Line 14: print(9 in unique_numbers)
Evaluate the print arguments from the current state and display them. sep controls separators and end controls the ending when those options are provided. Displaying a value does not return that value from the surrounding function.
Common mistake
if position incorrectly treats index 0 as absence. Use a distinct sentinel such as None.