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.com Feb 12 '17 at 18:13

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

  • $\begingroup$ Logarithms are taught in high school hereabouts. $\endgroup$ – Raphael Feb 12 '17 at 18:33
  • $\begingroup$ 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! $\endgroup$ – 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.

The mathematical preliminaries here should be covered in an intro discrete mathematics class.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy