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

From: Jens Axel Søgaard (jensaxel at soegaard.net)
Date: Mon Aug 24 13:18:48 EDT 2009

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

Posted on the users mailing list.