2
$\begingroup$

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?
$\endgroup$

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
2
$\begingroup$

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.

$\endgroup$

Your Answer

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