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

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?"


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

> 2009/8/24 David Yrueta <dyrueta at gmail.com>:
> > Hi All --
> >
> > I have a few questions concerning the section on abstract running time
> and
> > Big-O in HtDP, discussed here --
> > http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-36.html#node_sec_29.1
> >
> > First, I don't understand this statement, which relates to the function
> > "insert" (reproduced below) --
> > "Because there are N applications of insert, we have an average of on the
> > order of N2 natural recursions of insert."
> >
> > I tabled the results for 4 "worst-case" scenarios for sort: (list 1),
> (list
> > 1 2), (list 1 2 3) and (list 1 2 3 4) --
> > (list 1) -> sort=1 natural recursion (nr); insert=1 nr -> (list 1)
> > (list 1 2) -> sort=2 nr; insert=3 -> (list 2 1)
> > (list 1 2 3)  sort=3 nr; insert=6 nr -> (list 3 2 1)
> > (list 1 2 3 4) sort=4 nr; insert=10 nr (list 4 3 2 1)
> > Why are the number of natural recursion for insert described as an
> > exponential function of N?  I don't see it.
>
> So adding your results we get:
>  1+2+3+4 = 10
>
> In general we get:
>
>  1+2+3+4+...+n = 1/2*n*(n+1) = 1/2 n^2 + 1/2n
>
> The result is quadratic (not exponential) in n.
>
>
> --
> Jens Axel Søgaard
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090824/527f9fa8/attachment.html>