Hi All --<br><div><br></div><div>I have a few questions concerning the section on abstract running time and Big-O in HtDP, discussed here --</div><div><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 "insert" (reproduced below) --</div><div><br></div><div>"<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><br>
</div><div><span class="Apple-style-span" style="font-family: 'times new roman'; font-size: 16px;"><br></span></div><div>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) --</div>
<div><br></div><div>(list 1) -> sort=1 natural recursion (nr); insert=1 nr -> (list 1)</div><div>(list 1 2) -> sort=2 nr; insert=3 -> (list 2 1)</div><div>(list 1 2 3) sort=3 nr; insert=6 nr -> (list 3 2 1)</div>
<div>(list 1 2 3 4) sort=4 nr; insert=10 nr (list 4 3 2 1)</div><div><br></div><div>Why are the number of natural recursion for <span class="Apple-style-span" style="font-style: italic;">insert</span> described as an exponential function of N? I don't see it. </div>
<div><br></div><div>Second question refers to exercise 29.1.1. I'm assuming the definition of a number-tree follows the standard recursive structure, and is not just either "a number" or "a pair of number-trees." If so, I'm not sure how to measure tree sizes, or in other words, compare the size of this tree -- (list 1 2) -- to this tree -- (list (list empty) (list empty)). Do both have an N of 2? If so, is the abstract running time an average of the two? (I wrote the function sum-tree as the requested by the exercise, but am not posting it here out of regard for other students). </div>
<div><br></div><div>Third, with regards to exercise 29.2.1, must the constant c referred to in the discussion of Big-O be an integer, or can it be a fractional number? </div><div><br></div><div>;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; </div>
<div><br></div><div>;; sortr : list-of-numbers -> list-of-numbers<br>;; sorts a list-of-numbers in descending order<br>(define (sortr list-of-numbers)<br>
(cond<br> [(empty? list-of-numbers) empty]<br> [else (insert (first list-of-numbers)<br> (sortr (rest list-of-numbers)))]))<br>;; examples & tests<br>;; (check-expect (sortr (list 1 2 3)) (list 3 2 1))</div>
<div><br>;; insert : number (list-of-numbers) -> (list-of-numbers)<br>;; places number in descending order within a list of numbers<br>(define (insert a list-of-numbers)<br> (cond<br> [(empty? list-of-numbers)<br>
(list a)]<br>
[(> a (first list-of-numbers))<br> (cons a list-of-numbers)]<br> [else (cons (first list-of-numbers)<br> (insert a (rest list-of-numbers)))]))<br>;; examples & tests<br>;; (check-expect (insert 2 (list 3 1)) (list 3 2 1))</div>
<div><br></div><div>Thanks!</div><div>Dave Yrueta</div>
<div><br></div>
<div><span style="font-family:'times new roman';font-size:16px"><br></span></div><div><span style="font-family:'times new roman';font-size:16px"><div><br></div></span></div><div><span style="font-family:'times new roman';font-size:16px"><br>
</span><br></div>