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

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