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

2009/8/24 David Yrueta <dyrueta at gmail.com>:
> Thank you Jens.
> 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?"

Yes. Two functions f and g is said to have the same order of growth
if f(n)/g(n) -> c for n->infinity, where c is a non-zero constant.

This is indeed the case here, since

(1/2 n^2 + 1/2 n)/n^2 -> 1/2 for n->infinity.

-- 
Jens Axel Søgaard