JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Computational Complexity Question about Computation Complexity
 Question about Computation Complexity | Reply Hi,In first place, great article for the "Computational Complexity".I've some question about what's written in the article.1 - In the example 6 of section of the "More recursion trees", you say that in the second level of the tree, we've a complexity of c(N/2)^3. Why not c(N/3)^3?2 - Why the time to process each of them decreases to one eighth of the original time?3 - You say that the geometric progression has the sum of:S=cN^3/(1-3/8)Why do you put (1-3/8)? What do you want to say?4 - You say that in the example 6, "as we go deeper in the tree, the total amount of work on the current level decreases.", but in the example 7 "as we go deeper in the tree, the total amount of work on the current level increases.". Why the amount of work in 7 increases and in 6 decreases, if, on going to a deeper level in both examples, the problem is divided in more subproblems?Thanks,Pedro
 Re: Question about Computation Complexity (response to post by pedrosacosta) | Reply 1 - In the example 6 of section of the "More recursion trees", you say that in the second level of the tree, we've a complexity of c(N/2)^3. Why not c(N/3)^3?The recurrence in that example is: f(N) = 3f(N/2) + Theta(N^3).This means:1. we take a problem of size N and produce three (maybe completely different) problems of size N/2 each2. we separately (recursively) solve each of them3. we combine the results to get the result for the original problemSteps 1+3 together take time proportional to N^3. This is the work that gets assigned to the root node.In the second level, the same happens with problems of size N/2. For each of them, steps 1+3 will take time proportional to (N/2)^3.2 - Why the time to process each of them decreases to one eighth of the original time?Because (N/2)^3 = (1/8) * N^3, therefore the work in a node on the level X+1 is 1/8 of the work in a node on the level X, for any X.There are three times as many nodes on level X+1 than there are on level X. Thus the total work on level X+1 = 3 * (1/8) * the total work on level X, for any X.3 - You say that the geometric progression has the sum of:S=cN^3/(1-3/8)Why do you put (1-3/8)? What do you want to say?See, for example, http://en.wikipedia.org/wiki/Geometric_progression for a formula on the sum of a geometric progression.The formula for the sum of an infinite geometric progression is:sum = first_term / ( 1 - ratio )In our case, the ratio of the progression is 3/8, and the first term is cN^3.4 - You say that in the example 6, "as we go deeper in the tree, the total amount of work on the current level decreases.", but in the example 7 "as we go deeper in the tree, the total amount of work on the current level increases.". Why the amount of work in 7 increases and in 6 decreases, if, on going to a deeper level in both examples, the problem is divided in more subproblems?It's not only the number of nodes that matters, but also the work (steps 1+3) done in each of them. In example 6, there is quite a lot of work, and thus the top levels are the ones where most of the work gets done. In example 7, there is not much work, and thus the number of nodes will "overweigh" it and cause the bottom levels to contain most of the work.
 Re: Question about Computation Complexity (response to post by misof) | Reply Ok, I'm bumping an old thread but anyway... :-)Coming to example 6 under "More recursion trees", why are you summing the series till infinity? There are lg(N) levels, so shouldn't you be summing only the first lg(N) terms? If it doesn't matter, can you tell me why?Also, there is a typo in the graph at level 3, each vertex should be c(N/4)3Now, example 7, as you said, the total amount of work increases as we go deeper into the tree and so, most of the work is done at the lowest level. I don't understand why in this case you are not using the sum of a finite G.P formula? The only difference between example 6 and 7 is that you have a decreasing G.P in 6 and an increasing G.P in 7. I'm not sure if I'm missing something here!You calculated the work done at the last level (= c5log3N) and then, to compute the work done on all levels you reversed the G.P. What do you mean by "we now reversed it"?TL;DR - In both examples under "More recursion trees", why are you not using the sum of a finite G.P formula to calculate the total amount of work?
 Re: Question about Computation Complexity (response to post by TheGOAT) | Reply Gentle bounce!Any thoughts?