Numbers Every Software Engineer Should Know
This article is a collection of runtime and memory usage numbers that might be useful to keep in mind when building performance critical software.
Big-O Absolute Numbers
This chart shows how well or poorly certain algorithm complexities scale
when n grows.
Function | n=8 (2^3) | n=64 (2^6) | n=1024 (2^10) | n=2^32 (~ 4 billion)
-----------|-----------|-------------|---------------|---------------------
log(n) | 3 | 6 | 10 | 32
n | 8 | 64 | 1024 | 4294967296
n*log(n) | 24 | 384 | 10240 | 1.374...E11
n^2 | 64 | 4096 | 1048576 | 1.844...E19
n^2*log(n) | 192 | 24576 | 1.048...E7 | -
n^3 | 512 | 262144 | - | -
2^n | 256 | 1.844...E19 | - | -
n! | 40320 | 1.268...E89 | - | -
Runtime Performance Numbers
Big-O Runtime Performance Numbers
This chart shows how well or poorly certain algorithm complexities scale when n grows,
in the context of CPU runtime. Exponentials and factorial algorithms clearly
do not scale to values of n of any significant size.
Function | n=8 (2^3) | n=64 (2^6) | n=1024 (2^10) | n=2^32 (~ 4 billion)
-----------|-----------|------------------|---------------|---------------------
log(n) | 3 ns | 6 ns | 10 ns | 32 ns
n | 8 ns | 64 ns | 1 µs | 4.2 seconds
n*log(n) | 24 ns | 384 ns | 10 µs | 137 seconds
n^2 | 64 ns | 4 µs | 1 ms | 584 years
n^2*log(n) | 192 ns | 24 µs | 10 ms | forever
n^3 | 512 ns | 262 µs | 1 second | forever
2^n | 256 ns | 584 years | forever | forever
n! | 40 µs | forever | forever | forever
ns = Nanoseconds, about the time it takes for a CPU instruction cycle to run
µs = 1,000 ns
ms = 1,000 µs
forever = way way longer than the lifetime of the universe of 13.798 billion years
Latency Numbers
This chart shows the round trip latency for certain computing actions.
Action | Time | Comparisons
------------------------------------|----------|-----------------------------
L1 cache reference | 0.5 ns |
Branch mispredict | 5 ns |
L2 cache reference | 7 ns | 14x L1 cache
Mutex lock/unlock | 25 ns |
Main memory reference | 100 ns | 20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy | 3,000 ns |
Send 1K bytes over 1 Gbps network | 10 µs |
Read 4K randomly from SSD* | 150 µs |
Read 1 MB sequentially from memory | 250 µs |
Round trip within same datacenter | 500 µs |
Read 1 MB sequentially from SSD* | 1 ms | 4X memory
Disk seek | 10 ms | 20x datacenter roundtrip
Read 1 MB sequentially from disk | 20 ms | 80x memory, 20X SSD
Send packet CA->Netherlands->CA | 150 ms |
+ By Jeff Dean: http://research.google.com/people/jeff/
+ Originally by Peter Norvig: http://norvig.com/21-days.html#answers
+ Retrieved from Jonas Bonér: https://gist.github.com/jboner/2841832
Memory and Storage Numbers
Big-O Storage size
This chart shows how well or poorly certain algorithm complexities scale when n grows,
in the context of memory and storage.
Function | n=8 (2^3) | n=64 (2^6) | n=1024 (2^10) | n=2^32 (~ 4 billion)
-----------|-----------|---------------|---------------|---------------------
log(n) | 3 B | 6 B | 10 B | 32 B
n | 8 B | 64 B | 1 KB | 4 GB
n*log(n) | 24 B | 384 B | 10 KB | 128 GB
n^2 | 64 B | 40 KB | 1 MB | 16 exabytes
n^2*log(n) | 192 B | 24 KB | 10 MB | ...
n^3 | 512 B | 256 KB | 1 GB | ...
2^n | 256 B | 16 exaBytes | ... | ...
n! | 40 KB | ... | ... | ...
B = 1 Byte, or 8 Bits
KB = kilobyte (1024 B)
MB = megabyte (1024 KB)
GB = gigabyte (1024 MB)
TB = terabyte (1024 GB)
TB = petabyte (1024 TB)
exabyte = 1024 petabytes, or 1 million computers with 1 terabyte HDs
... = there isn't enough room on earth to store the required computers.
Powers of Two Table
This chart shows how much memory is required to store bits in powers of two. For example, it takes 4GB of memory to store 232 bits in memory, and would require 16GB of memory to store an array of 32-bit integers. This is useful for knowing when a hash table is appropriate for a problem.
Power of 2 | Exact Value | Storage size
-----------|-------------------|-------------
7 | 128 | 128 B
8 | 256 | 256 B
10 | 1024 | 1 KB
16 | 65,536 | 64 KB
20 | 1,048,576 | 1 MB
30 | 1,073,741,824 | 1 GB
32 | 4,294,967,296 | 4 GB
40 | 1,099,511,627,776 | 1 TB
64 | 1.844...E19 | 16 exabytes
+ Modified from _Cracking the Coding Interview_ By Gayle L. McDowell (p. 47)