Time & Space Complexity

Easy

Big-O · how cost grows with input

In simple words

Big-O is just a way to say how much slower a job gets when you give it more to do — like how a longer line means a longer wait.

The idea

Big-O describes how the running time or memory grows as the input gets large, ignoring constants. Compare algorithms by their dominant term: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).

The trick

Count the work in the deepest loop, then see how it scales with n.
Drop constants and lower-order terms — only the fastest-growing term matters.
Three bounds: Big-O is the worst-case ceiling (≤), Big-Ω the best-case floor (≥), and Big-Θ the tight bound when they match.
Space complexity = input + auxiliary + output; we usually quote just the auxiliary (extra) space an algorithm allocates.

←→stepspaceplay

1/7

Optimal

time—space—

Read loops to estimate cost.

1for (i in n)            // O(n)2for (i in n) for (j in n)   // O(n²)3while (n → n/2)          // O(log n)4sort(arr)               // O(n log n)

Input

array: [1, 3, 8, 24, 64]

Memory

O(n log n): —
O(n²): —

Output

O(1): —
O(log n): —
O(n): —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: for i in 0..n-1: for j in 0..n-1: work()
Output:: O(n²) time, O(1) space
Explanation:: The inner line runs n times for each of n outer turns, so the count is n·n. Nothing is stored, so the space is a constant.

Example 2

Input:: while n > 0: n = n / 2
Output:: O(log n) time
Explanation:: Halving 1000 reaches 1 in about ten steps, not a thousand. Every doubling of the input adds one step, which is what log n means.

Finished the walkthrough? Add it to your streak.