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

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).
"Because there are *N* applications of insert, we have an average of on the
order of *N*2 natural recursions of insert."
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 -- 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?
Thanks,
Dave
On Mon, Aug 24, 2009 at 10:18 AM, Jens Axel Søgaard
<jensaxel at soegaard.net>wrote:
>* 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
*>*
*-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090824/dcaebe86/attachment.html>