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

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 *N*2 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.

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).

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?

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; sortr : list-of-numbers -> list-of-numbers
;; sorts a list-of-numbers in descending order
(define (sortr list-of-numbers)
  (cond
    [(empty? list-of-numbers) empty]
    [else (insert (first list-of-numbers)
                  (sortr (rest list-of-numbers)))]))
;; examples & tests
;; (check-expect (sortr (list 1 2 3)) (list 3 2 1))

;; insert : number (list-of-numbers) -> (list-of-numbers)
;; places number in descending order within a list of numbers
(define (insert a list-of-numbers)
  (cond
    [(empty? list-of-numbers)
     (list a)]
    [(> a (first list-of-numbers))
     (cons a list-of-numbers)]
    [else (cons (first list-of-numbers)
                (insert a (rest list-of-numbers)))]))
;; examples & tests
;; (check-expect (insert 2 (list 3 1)) (list 3 2 1))

Thanks!
Dave Yrueta
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090824/4dda9494/attachment.html>