[prev in list] [next in list] [prev in thread] [next in thread] 

List:       racket-users
Subject:    [BULK] [plt-scheme] HtDP Section 29 -- Abstract Running Time & Big-O
From:       sbloch () adelphi ! edu (Stephen Bloch)
Date:       2009-08-24 20:49:12
Message-ID: 3D56E89A-3F66-4AD1-9E75-1003025D708B () adelphi ! edu
[Download RAW message or body]


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





[prev in list] [next in list] [prev in thread] [next in thread]