liveBook · Manning

Linear time complexity

As explained in Python Workout: 50 ten-minute exercises

An asymptotic time complexity that grows proportionally with the number of elements processed.

Linear time complexity describes work that grows with the number of elements processed. Searching a string, list, or tuple one element at a time takes O(n): longer sequences require proportionally more searching. section 4.1

Python’s in operator provides a readable way to perform this kind of search. It effectively examines sequence elements in turn, making linear time a practical choice for many short strings and collections. section 2.3

Checking for a vowel

Instead of repeating comparisons for every vowel, use `if word[0] in 'aeiou':`. The concise form preserves the linear-search behavior while improving readability. section 2.3

if word[0] in 'aeiou':

Compare the idiomatic membership test with longer repeated-condition and explicit-loop alternatives. section 2.3

How Python Workout: 50 ten-minute exercises covers it

How deep it goes
Defines O(n), illustrates proportional growth, and stops short of detailed complexity analysis or implementation internals.
Examples
Uses an office-search analogy, vowel detection, Pig Latin processing, and Python membership code.
What you can do after
Apply linear-time membership tests to Python sequences and recognize when their cost is acceptable.
How it connects
Connects sequence search with strings, lists, tuples, dictionaries, hash functions, and constant time.

Also explained in

Compare how 8 books explain linear time complexity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Python Workout: 50 ten-minute exercises. The section links point to the parts of the book it draws on.