Units of space and time

Now that we know algorithmic efficiency is measured along the axes of space and time, it's also helpful to know how these resources are measured.

Measuring time

In the password-guessing example, we took a computationally intensive problem and thought about how long it would take to complete, which allowed us to measure the result in terms of quadrillions of years. However, time-based measurements of computer operations are typically on a much smaller scale:

In other words, the following are equivalent:

1 ns = 10^-9 seconds
1 us = 10^-6 seconds = 1,000 ns
1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns
1 s = 1,000 ms = 1,000,000 us = 1,000,000,000 ns

The amount of time it takes for a process to complete is called its latency. We give some example latency measurements at the end of this lesson.

Measuring space

We have specific units for measuring the amount of space that data takes up. The most basic unit to measure volume of data is the bit (binary digit) -- a 0 or 1. Groups of 8 bits are often referred to as a byte.

For example, the ASCII encoding of characters assigns 8 bits (1 byte) for each Latin alphabet character. The letter 'A' has the binary encoding 01000001.

Larger groups of bits and bytes use the metric prefixes. For example:

⚠️ But be careful! Always be aware of whether you're measuring something in terms of bits or bytes. Typically, values measured in bits are represented with a lowercase "b" or "bits," e.g., 100 Kb or 100 Kbits. Values measured in bytes are usually represented with an uppercase "B" or "bytes," e.g., 100 KB or 100 Kbytes. If precision matters for your task, it's better to explicitly use "bits" or "bytes" to clearly communicate.

Base 2 and base 10

As shown above, the prefixes "kilo," "mega," "giga," and "tera" correspond to powers of 10: 10³, 10⁶, 10⁹, and 10¹². However, when we say that a computer has 8 GB of RAM, we actually do not mean that it has 8 x 10⁹ bytes!

This is because volumes of memory and storage are conventionally measured in powers of 2 (binary), not powers of 10 (decimal). Quite luckily, some powers of 2 are almost equal to some powers of 10, so the difference is often insignificant. Units that are based on powers of 2 have slightly different prefixes:

Because the difference between, say, a KB and a KiB is so small, "KB" could be used to mean either one. Again: if precision matters, be overtly clear about which unit you're using.

To make matters even more confusing, telecommunications systems measure properties such as Internet bandwidth using the power of 10 system. A 1 Gbps connection means that 1 x 10⁹ bits of information can be transmitted in one second.

Why the difference? Well, telecommunications and storage technologies evolved separately and without a consistent standard, leading to different conventions for units that continues today!

Putting it all together

Now that we know about the memory hierarchy and the different ways of measuring space and time, we can ground our understanding of these concepts with some concrete numbers:

Knowing these exact figures is not crucial to being able to write algorithms and use data structures. But it's helpful to know the scale at which we're working, and how the physical components of a computer will affect our programs.