Thank you Jens.<div><br></div><div>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?" </div><div>
<div><br></div><div><br><div class="gmail_quote">On Mon, Aug 24, 2009 at 8:14 AM, Jens Axel Søgaard <span dir="ltr"><<a href="mailto:jensaxel@soegaard.net">jensaxel@soegaard.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
2009/8/24 David Yrueta <<a href="mailto:dyrueta@gmail.com">dyrueta@gmail.com</a>>:<br>
<div class="im">> Hi All --<br>
><br>
> I have a few questions concerning the section on abstract running time and<br>
> Big-O in HtDP, discussed here --<br>
> <a href="http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-36.html#node_sec_29.1" target="_blank">http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-36.html#node_sec_29.1</a><br>
><br>
> First, I don't understand this statement, which relates to the function<br>
> "insert" (reproduced below) --<br>
> "Because there are N applications of insert, we have an average of on the<br>
> order of N2 natural recursions of insert."<br>
><br>
> I tabled the results for 4 "worst-case" scenarios for sort: (list 1), (list<br>
> 1 2), (list 1 2 3) and (list 1 2 3 4) --<br>
> (list 1) -> sort=1 natural recursion (nr); insert=1 nr -> (list 1)<br>
> (list 1 2) -> sort=2 nr; insert=3 -> (list 2 1)<br>
> (list 1 2 3) sort=3 nr; insert=6 nr -> (list 3 2 1)<br>
> (list 1 2 3 4) sort=4 nr; insert=10 nr (list 4 3 2 1)<br>
> Why are the number of natural recursion for insert described as an<br>
> exponential function of N? I don't see it.<br>
<br>
</div>So adding your results we get:<br>
1+2+3+4 = 10<br>
<br>
In general we get:<br>
<br>
1+2+3+4+...+n = 1/2*n*(n+1) = 1/2 n^2 + 1/2n<br>
<br>
The result is quadratic (not exponential) in n.<br>
<br>
<br>
--<br>
<font color="#888888">Jens Axel Søgaard<br>
</font></blockquote></div><br></div></div>