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

Popular posts from this blog

html - Outlook 2010 Anchor (url/address/link) -

javascript - Why does running this loop 9 times take 100x longer than running it 8 times? -

Getting gateway time-out Rails app with Nginx + Puma running on Digital Ocean -