Space Complexity

Big-O tells you how memory grows; this calculator tells you how much it actually is — bytes, KB, MB and GB for n elements of a given size.

How the calculation works

Space complexity describes how an algorithm's memory use scales with input size. O(n) captures the growth rate but not the number of megabytes. Here the payload is computed directly: memory = n × b, where n is the number of elements and b is the size of one element in bytes.

Common values for b: 1 byte for char/uint8, 4 bytes for int32 and float, 8 bytes for int64, double and a pointer on a 64-bit platform. The result uses binary units: 1 KB = 1,024 bytes, 1 MB = 2²⁰ = 1,048,576 bytes and 1 GB = 2³⁰ bytes — strictly speaking KiB, MiB and GiB under IEC 80000-13.

For structures with other complexities, plug the real element count into n: n² for an n×n matrix, vertices plus edges for an adjacency list. Container overhead and alignment padding are not included, as the result note reminds you.

Worked example

An array of 1,000,000 int32 values (4 bytes each): 1,000,000 × 4 = 4,000,000 bytes = 3,906.3 KB ≈ 3.81 MB ≈ 0.004 GB. Store the same values as int64 or double (8 bytes) and you get 8,000,000 bytes ≈ 7.63 MB — exactly twice as much.

Things to keep in mind

• Boxed values cost far more: in CPython each list slot is an 8-byte pointer plus a separate int object (about 28 bytes for small numbers).
• Dynamic arrays (std::vector, ArrayList, Python list) keep spare capacity, and hash tables leave buckets empty on purpose — budget extra headroom.
• Recursive algorithms use stack space too: recursion depth × frame size counts toward space complexity.
• Distinguish auxiliary space (extra memory beyond the input) from total space: merge sort needs O(n) auxiliary memory, heapsort O(1).