O(n)

Theory → Algorithmic Analysis

Big O Notation

A notation for describing how resource usage grows as input size increases.

Where it fits

Big O notation belongs to algorithmic analysis. It describes how resource usage grows as input size grows.

Mental model

Big O ignores constant details and focuses on growth shape. It helps compare algorithms before implementation details dominate the discussion.

Example

A linear scan is O(n): doubling the input roughly doubles the work. Binary search is O(log n): doubling the input adds about one extra step.

Common mistakes

Treating Big O as exact runtime.
Ignoring constants and real hardware when they matter.
Comparing algorithms without considering input size and data distribution.

Time complexity, space complexity, algorithms, binary search.