performance - calculate a running time of a function -
i have trouble coming running time of function calls other functions. example, here function convert binary tree list:
(define (tree->list-1 tree) (if (null? tree) ’() (append (tree->list-1 (left-branch tree)) (cons (entry tree) (tree->list-1 (right-branch tree))))))
the explanation t(n) = 2*t(n/2) + o(n/2) because procedure append takes linear time. solving above equation, t(n) = o(n * log n).
however, cons procedure combines 2 element. in case goes though entry node, why don't add o(n) in solution?
thank help.
consider o(n^2)
quadratic. consider o(n^2 + n)
, still quadratic, hence can reduce o(n^2)
+ n
not significant (it not change "order of magnitude" (not sure right term)).
the same applies here can reduce o([n*log(n)] + n)
o(n*log(n))
. may not reduce o(log(n))
logarithmic, not.
Comments
Post a Comment