[BULK] [plt-scheme] HtDP Section 29 -- Abstract Running Time & Big-O

On Aug 24, 2009, at 9:37 AM, David Yrueta wrote:

> "Because there are N applications of insert, we have an average of  
> on the order of N2 natural recursions of insert."

There's some hand-waving going on behind this sentence, hiding the  
fact that \Sigma_{i=1}^n i is n(n+1)/2, which is O(n^2) after  
ignoring constants.

> Third, with regards to exercise 29.2.1, must the constant c  
> referred to in the discussion of Big-O be an integer, or can it be  
> a fractional number?

It doesn't matter.  If the statement is true with a fractional  
number, then it's also true for the next larger integer.

Stephen Bloch
sbloch at adelphi.edu