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

Okay, but I'm still a bit hung up on the way N^2 for insert was informally
derived by HtDP (if I'm using the terminology incorrectly, please bear with
me -- this is my first encounter with notions of growth rates, etc).
 "Because there are *N* applications of insert, we have an average of on the
order of *N*2 natural recursions of insert."

Is the point to accept this and move on, or am I missing something
important? As I mentioned before, I counted 10 applications of insert for an
input of N=4.  You derived that same result (I think) by adding the number
of elements in the list which insert progressively traverses -- 1+2-3+4=10
-- turning that into a quadratic equation which accepts the number of
elements in the list -- 1/2 n^2 + 1/2n -- and outputs abstract running times
(N=4; abstract running time = 10).  We took the abstract running time as "on
the order of n^2" because, as Eugene says, "we ignore the coeeficients
because, as n grows, they matter less and less."  Am I in the ballpark?

Thanks,
Dave



On Mon, Aug 24, 2009 at 10:18 AM, Jens Axel Søgaard
<jensaxel at soegaard.net>wrote:

> 2009/8/24 David Yrueta <dyrueta at gmail.com>:
> > Thank you Jens.
> > So it is correct to say with HtDP that "there is an average of on
> the order
> > of N^2 natural recursions of insert" by ignoring the constants in "1/2
> n^2 +
> > 1/2n?"
>
> Yes. Two functions f and g is said to have the same order of growth
> if f(n)/g(n) -> c for n->infinity, where c is a non-zero constant.
>
> This is indeed the case here, since
>
> (1/2 n^2 + 1/2 n)/n^2 -> 1/2 for n->infinity.
>
> --
> Jens Axel Søgaard
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090824/dcaebe86/attachment.html>