Unit cost vs. bit cost in time complexity

yourbasic.org
Unit-cost multiplication devise.
Unit-cost multiplication

Unit cost and bit cost are two different cost functions used to compute space and time complexity.

Unit cost often works well in practice as modern processors can perform arithmetics on 64-bit integer and floating point numbers in constant time.

Unit cost example

func Add(x, y int64) int64 {
    return x + y
}

In this simple example it’s sensible to use unit cost and say that the function runs in constant time.

Bit cost example

func Concatenate(x, y string) string {
    return x + y
}

Here it would be a mistake to use unit cost for the + operation: to concatenate two strings, we must allocate new memory and copy the characters.

In this case it’s better to use bit cost for the + operation:

Note that we still use unit cost for character operations. This makes perfect sense as characters can be represented by small fixed-sized integers.

Share this page: