Re: [sicp-vsg] Gripe about "orders of growth" explanation
> There is no further discussion of k1f(n) and k2f(n), as far asBut k's are just arbitrary constants?
> I know. I find this annoying and frustrating.
> In any event, the authors themselves say in footnote 36, "TheseBut they also continue on to say in the same footnote why it's an
> statements mask a great deal of oversimplification."
oversimplification. While an algorithm might be theta(log n) it
doesn't account for procedures it uses that might grow at changing
rates themselves, like multiplication of large numbers. If for some
reason those steps somehow were more than log n, then your algorithm's
no longer theta(log n).
It's also an oversimplification of the idea of steps, since you're not
really counting steps, just their order of growth. As they said,
things that grow at n^2, 3n^2 and say, n^2 + 1000n + 50000 are all
> If not, then where did 14 come from? If anybody knows how to deriveTheir footnote kind of explains it. 14 multiplications comes from
> 14, I'd like them so show me how. (I.e., given what has been
> said previously about orders of growth, prove that a process that
> grows by theta(log n)for n = 1000 will require exactly 14
"More precisely, the number of multiplications required is equal to 1
less than the log base 2 of n plus the number of ones in the binary
representation of n. This total is always less than twice the log base
2 of n."
They derived this informally from the definition of fast-expt, afaict.
When do multiplications occur? The even? cases total up to log n of
base 2, which they've explained before. The odd case is every time
you meet an odd n, which is the same as saying the number of 1's in
the binary representation of n (dividing a binary number by 2 is the
same as shifting it left once).
> Similarly, I see an "empirical" approach in Exercise 1.22. (OrNothing's wrong with the empirical approach here, they were just
> maybe the term should be "pragmatic.") I'm referring to the
> idea of confirming a theoretical prediction with an experiment,
> in this case timing the test for primality against the system
trying to have you explore whether or not the number of "steps" in a
process relates directly to the time it takes to complete on your
computer. AFAIK, this isn't necessarily true depending on how your
machine is implemented.
> Another way of putting the above is to say that the authorsI think it can be omitted only because it's not totally important
> are not living up to their aim of presenting a "procedural
> epistemology." (See Preface to the First Edition, p. xviii.)
> According to that, the mathematics of orders of growth could
> just be omitted. The reader should be more interested in "how to"
> than in "what is."
until you have problems with different algorithms that have different
orders of growth and you have to use orders of growth as a way of
comparing them. Sorting is the canonical example but in real life,
you might be looking at the same thing with some other problem.