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

On Aug 24, 10:47 am, David Yrueta <dyru... at gmail.com> wrote:
> 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."
>

N applications of insert but the size of the problem decreases by one
on every iteration so the sum is a triangle number ( a search on that
term will probably yield a derivation of the formula Jens mentioned in
his first reply).