# integer = c lg n (inputs of size n, Cormen 3rd, page 23)?

I just started with my "Algorithms" course. But my CS-background is lower than that of an average CS-student (I'm a data science student). Only had intro-2-prog course (Python/Java), that's it.

Cormen states on page 23: "...when working with inputs of size n, we typically assume that integers are represented by c lg n bits..."

• How is " c lg n " derived? It's relation to the input size?
• What calculation/proof is made here?
• Which assumptions should one have to come to this assumption?
• Which CS-field/subject (or academic/uni course?) works/operates with this notation, that should be learned prior to the "Algorithms" couse?

## migrated from stackoverflow.comFeb 12 '17 at 18:13

This question came from our site for professional and enthusiast programmers.

• Logarithms are taught in high school hereabouts. – Raphael Feb 12 '17 at 18:33
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Feb 12 '17 at 18:34

lg n is the base-2 logarithm of n, satisfying 2^lg n = n, so about lg n bits (ceil lg n to be exact) are needed for integers that can represent 0..n-1, which suffices for pointers into the input. The authors of CLRS are saying that the word size should be about this much (c lg n). This is arguably reasonable because c lg n-bit words index storage of n^c (so any polynomial in n), and c lg n-bit operations can be synthesized from lg n-bit operations in constant time. If we make the word size much bigger, then the implied data-parallelism starts to distort running times.