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). <div>
<br></div><div> <span class="Apple-style-span" style="border-collapse: collapse; ">"<span style="font-family: 'times new roman'; font-size: 16px; ">Because there are <em>N</em> applications of <code style="color: rgb(165, 42, 42); "><span style="color: navy; ">insert</span></code>, we have an average of on the order of <em>N</em><sup>2</sup> natural recursions of <code style="color: rgb(165, 42, 42); "><span style="color: navy; ">insert</span></code>."</span></span></div>
<div><font class="Apple-style-span" face="'times new roman'" size="4"><span class="Apple-style-span" style="border-collapse: collapse; font-size: 16px;"><br></span></font></div><div><font class="Apple-style-span" face="'times new roman'" size="4"><span class="Apple-style-span" style="border-collapse: collapse; font-size: 16px;">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 -- <span class="Apple-style-span" style="font-family: arial; font-size: 13px; ">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?</span></span></font></div>
<div><span class="Apple-style-span" style="border-collapse: collapse;"><br></span></div><div><span class="Apple-style-span" style="border-collapse: collapse;">Thanks, </span></div><div><span class="Apple-style-span" style="border-collapse: collapse;">Dave </span></div>
<div><div><br></div><div><br><br><div class="gmail_quote">On Mon, Aug 24, 2009 at 10:18 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;">
<div class="im">2009/8/24 David Yrueta <<a href="mailto:dyrueta@gmail.com">dyrueta@gmail.com</a>>:<br>
</div><div class="im">> Thank you Jens.<br>
> So it is correct to say with HtDP that "there is an average of on the order<br>
> of N^2 natural recursions of insert" by ignoring the constants in "1/2 n^2 +<br>
> 1/2n?"<br>
<br>
</div>Yes. Two functions f and g is said to have the same order of growth<br>
if f(n)/g(n) -> c for n->infinity, where c is a non-zero constant.<br>
<br>
This is indeed the case here, since<br>
<br>
(1/2 n^2 + 1/2 n)/n^2 -> 1/2 for n->infinity.<br>
<br>
--<br>
<font color="#888888">Jens Axel Søgaard<br>
</font></blockquote></div><br></div></div>