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

Popular posts from this blog

java - WARN : org.springframework.web.servlet.PageNotFound - No mapping found for HTTP request with URI [/board/] in DispatcherServlet with name 'appServlet' -

this question has answer here: why spring mvc respond 404 , report “no mapping found http request uri […] in dispatcherservlet”? 3 answers i trying making simple bbs i'm encountering following error, warn : org.springframework.web.servlet.pagenotfound - no mapping found http request uri [/board/] in dispatcherservlet name 'appservlet' i have tried solve error many times, have failed. how can solve error? here web.xml, controllerand , servlet-context. my web.xml <?xml version="1.0" encoding="utf-8"?> <web-app version="2.5" xmlns="http://java.sun.com/xml/ns/javaee" xmlns:xsi="http://www.w3.org/2001/xmlschema-instance" xsi:schemalocation="http://java.sun.com/xml/ns/javaee http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd"> <filter> <filter-nam...
Read more

1111. appearing after print sequence - php -

morning, i have code takes string of shoe sizes, explodes , puts in table. code works , info displayed correctly on page after table there few 1's after table. i'm confused this. so table looks (in columns of 3 on webpage) available in following sizes: 3 4 5 6 9 10 111 here's codes, purpose of example $x = 3|4|6|10|9 function get_sizes_pipe($x) { $counter = 0; $splits = explode("|",$x); asort($splits); $x = print "<table class='greentable'>"; $x .= print "<thead><tr><th scope='col' colspan='3' abbr='starter'>available in following sizes:</th></tr></thead><tbody><tr>"; foreach ($splits $split) { $entry = print "<td>".$split."</td>"; if($counter == 2){ $entry .= print "</tr><tr>"; $counter =0; } else { $counter++; ...
Read more

android - How to create dynamically Fragment pager adapter -

i unable create dynamic layout each tabs, able create tabs dynamically constructor(public mypageradapter(fragmentmanager fm , int nooftabs)), coudn't inflate view each tabs creating each fragment should dyanmic. public class mypageradapter extends fragmentpageradapter { private final string[] titles = { "categories", "home", "top paid", "top free", "top grossing", "top new paid", "top new free", "trending" }; int nooftabs; **public mypageradapter(fragmentmanager fm , int nooftabs) { super(fm); this.nooftabs = nooftabs; }** /*public mypageradapter(fragmentmanager fm) { super(fm); }*/ @override public charsequence getpagetitle(int position) { return titles[position]; } @override public int getcount() { ...
Read more