9
$\begingroup$

My lecturer says that a variable takes up one memory position in RAM. This is the slide in question:

But CLRS (Introduction to Algorithms by Cormen, end of page 23) says an integer is represented by $c\ lg\ n$.

Are both statements true? How can that be?

Improve this question
$\endgroup$
13
  • $\begingroup$ Seems there are in view different things - can you, firstly, exactly point to page in CLRS? $\endgroup$
    – zkutch
    Commented Apr 18, 2021 at 19:58
  • $\begingroup$ @zkutch page 23 $\endgroup$
    – Bee
    Commented Apr 18, 2021 at 20:21
  • 8
    $\begingroup$ @Bee both your professor and the CLRS text is correct. Although others have written wonderfully nice answers, I felt like explaining in an alternate manner. See the term memory position used by your professor has no units specified explicitly, but intuitively by using the common meaning, it can thought as memory word which is actually measured in bits. In real world computers all the data types like int, float, double have a fixed data size and as such the bits required to store them are constant and taking this constant number of bits as a memory position, your professor explains. $\endgroup$
    – Abhishek Ghosh
    Commented Apr 18, 2021 at 21:13
  • 5
    $\begingroup$ @Bee, while CLRS being mostly a mathematics books and to make things more generalized, it does not assume any limits on the size of n. So it states that to store an integer of size n we need $\Theta(\lg n)$ no. of bits. Note the units, and the concept that here the size of the bits required to represent an integer is not bounded , rather it is allowed to be variable with respect to n $\endgroup$
    – Abhishek Ghosh
    Commented Apr 18, 2021 at 21:15
  • $\begingroup$ @AbhishekGhosh thanks for the explanation. I'm starting to understand now. If you don't mind, could you please explain why an integer requires lg n bits? I've read elsewhere that lg n equals the number of binary digits used to represent an integer. however, the integer 2 = lg 2 = 1, but in binary form, 2 is written as 10, which is two digits? $\endgroup$
    – Bee
    Commented Apr 18, 2021 at 22:08

5 Answers 5

Reset to default
21
$\begingroup$

The random-access machine is a common model of computation, which is the model of choice when analyzing algorithms. In this model, memory consists of words of length $\Theta(\log n)$ bits, where $n$ is the length of the input (in bits). Therefore both your lecturer and CLRS are right.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Note that it is important to understand what exactly your particular algorithm is doing - in many cases indeed using "values" of fixed width is fine. Analyzing complexity of general a^b or even a*b would generally require to explicitly represent values as sequence of "memory positions" (and than you find that limiting the input's width bring you back to "value fits into one memory element). Fortunately there are much more cases where all results have limited values (even most algorithms crypto has max "word" size for involved operations - thousands bits long but a fixed upper bound anyway). $\endgroup$
    – Alexei Levenkov
    Commented Apr 19, 2021 at 19:24
  • $\begingroup$ Is the log base the size of the input, or the size of the memory? I would think the latter would make more sense, especially since the basic primitive operations in the random-access model would be reading or writing a storage location by index, which would require an index that was capable of holding values up to n-1. In some cases it may make sense to describe algorithms which use an indexable array of bits, but in most cases it makes sense to say that all storage locations are large enough to hold an index. $\endgroup$
    – supercat
    Commented Apr 20, 2021 at 21:26
  • $\begingroup$ Usually we're interested in polynomial time algorithms, and then it doesn't matter whether $n$ is the size of the input or the amount of space used by the algorithm. $\endgroup$
    – Yuval Filmus
    Commented Apr 21, 2021 at 5:14
13
$\begingroup$

In practical computer machines (aka, real-world computers) variables can be considered to be stored in "one" memory position, since the variable's size is fixed beforehand. For example, int is usually 32 bit long, and hence we can say it takes up "one" memory position of length 32 bits.

However, in the theoretical terms, integers do not have to be bounded between some arbitrary values we defined beforehand. That is, in the practical world integer with size 32 bit cannot store a value larger than $2^{32}-1$, but in the theoretical model it can. The caveat here, is that since we do not restrict the value of a variable, we need to actually consider how much memory it eats up. To save the number $n$ we need $\log(n)$ bits, hence what the book says is true, in the theoretical model.

Improve this answer
$\endgroup$
7
  • $\begingroup$ If you need it for theory of computer science, then probably the $\log(n)$ is the way to think of it. Try thinking combinatorically, how many numbers can $k$ bits represent? if we say it does represent all the numbers between $0$ and $n$, then what is $k$ in relation to $n$? $\endgroup$
    – nir shahar
    Commented Apr 18, 2021 at 19:45
  • $\begingroup$ But if we change the hardware & compiler a bit, we could have 64, 128, or I believe even 256 bit integers. Perhaps even 512 bit: see Intel's AVX-512: en.wikipedia.org/wiki/AVX-512 $\endgroup$
    – jamesqf
    Commented Apr 19, 2021 at 3:35
  • 1
    $\begingroup$ "variables can be considered to be stored in 'one' memory position" - except for strings in many languages, and integers in a few languages, and other classes/constructs that represent collections of other variables, unbounded numbers or other things. Unless by "the variable's size is fixed beforehand" you mean when the variable is created as opposed to all variables of that type being the exact same size, but from that it pretty much immediately follows that the entire computer memory is O(1), which would basically defeat the point of asymptotic analysis of code. $\endgroup$
    – Bernhard Barker
    Commented Apr 19, 2021 at 10:21
  • 2
    $\begingroup$ @Davor A class consisting only of a fixed number of fixed-size primitives would still be fixed-size, while what could arguably be called "primitives" in some languages are variable size (e.g. int in Python). $\endgroup$
    – Bernhard Barker
    Commented Apr 19, 2021 at 12:34
  • 2
    $\begingroup$ What's written here isn't always strictly true. Analysis of both theoretical algorithms and actual code sometimes ignore the fact that integers are technically O(log n) and just leave it at O(1) when the size of the value isn't significant enough to care about or won't change the overall complexity. This applies especially when we do something with the length of an array, string or whatever else represents our input as opposed to having the number itself be the input or output of the algorithm, and we similarly sometimes assume a number in a collection is O(1), yet theoretically unbounded. $\endgroup$
    – Bernhard Barker
    Commented Apr 19, 2021 at 13:15
3
$\begingroup$

In mathematics, an integer can get arbitrarily big. However, the bigger a number, the more digits are needed to write it down.

A memory cell in a computer has finite capacity. Therefore, a single cell can only store integers up to a certain size.

A single variable, stored in a single memory cell, can therefore hold integers only up to a certain size. That's why most programming languages limit the size of their integral data types. For instance, in Java, a variable of type int can hold integers up to $2^{31}$ (about 2 billion).

That is, the word "integer" means something slightly different in mathematics and programming. CLRS was talking about the mathematical integers, while your professor was talking about the integral data types provided by a computer. The former may get arbitrarily big, and require many memory cells, while the latter fit within a cell by definition.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ I'll note that there is some overlap. "BigInteger" type classes supporting arbitrarily large numbers typically use O(logn) bits. $\endgroup$
    – Brian
    Commented Apr 19, 2021 at 17:19
2
$\begingroup$

Integers take up logarithmic space but this is usually of little interest during algorithmic analysis of real-world problems.

Here are things to keep in mind:

1. Not the same $n$

The $n$ often used in Big-O notation conventionally refers to the number of data items, rather than the possible range of those items. For example, if you are sorting 50000 integers and they are all smaller than 2 billion, that's $n=50000$ and $m=2000000000$. The input data will consume $O(n\,\text{log}\,m$) space. But often this will just be expressed as $O(n)$ because in the real world it's rarely important to consider mind-bogglingly-huge integers which is what it would take to make a serious difference here.

2. Most algorithms are comparably affected by datum size

One of the main reasons to perform asymptotic analysis is to compare two algorithms which solve the same problem. Most important classes of algorithm, such as sorting and searching and graph algorithms (e.g. shortest-path etc.) and optimisation algorithms, generally have the same asymptotic complexity whether they are operating on say 32 or 64 bits.

3. There are exceptions

If we consider things like very large prime number testing, the size of the primes can be crucial to accurately characterise an algorithm's behaviour.

Also, in abstract or theoretical environments it is necessary to be more rigorous about such things. Turing Machines typically have a fairly small alphabet (i.e. "variables" can hold a quite small range of values) so it is impossible to hand-wave away the size of an int.

4. Many languages use variable-sized integers by default

In Python, Ruby, Haskell and Raku, an integer is automatically allocated as much memory as it needs. You can multiply 999999999 * 999999999 * 999999999 * 999999999 in any of these languages and get a 100% precise result—they are not floating-point numbers. So if you create an array of really big integers you will see logarithmic memory usage. (CPU operations will also increase if the numbers are larger!)

5. In practice, integer size (or numerical precision generally) is usually about machine selection, not algorithm selection.

If you are trying to process 20-digit numbers on an 8-bit computer, you are using the wrong machine. You will experience a blowout of both RAM and CPU operations. The solution is not a change of algorithm but a change of hardware.

6. Sparse integers can usually be collapsed with e.g. hashing

Algorithms that require several copies of very large integers to be stored can be modified to save memory by hashing the datum or using indices/pointers. This step does not increase big-O performance complexity (although it does slow things down.) Figuring out the right trade-off to make is not really something that can be captured in a simple big-O formula.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your example for point 4 can be shortened to 999999999**4 in the given languages (except Haskell, where ** becomes ^). $\endgroup$
    – J.G.
    Commented Apr 20, 2021 at 13:29
0
$\begingroup$

A variable refers to exactly one memory position, where "one memory position" is typically 64 bits on a modern computer.

When you want to store something bigger in a variable, you store a reference to the value in the original memory position. This reference can be used to find a sequence of memory positions that contain the actual value.

These extra memory positions do not belong to the variable, but to the value stored.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.