JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
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 each
2. we separately (recursively) solve each of them
3. we combine the results to get the result for the original problem

Steps 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)3

Now, 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?
Re: Question about Computation Complexity (response to post by TheGOAT) | Reply
Bouncing this thread, again!
Re: Question about Computation Complexity (response to post by TheGOAT) | Reply
Remember that we only care about asymptotic complexity, nothing else. Constants are completely irrelevant, so the methods that misof is trying to demonstrate are for finding that asymptotic behavior in a simple way. You're correct that the true total of the work in a recursion is represented by a finite sum, but since we only concern ourselves with the highest-order (dominating) terms, we can exercise a bit of cleverness to dodge the need for evaluating any series at all.

In example 6, since the total amount of work is falling with each progressive level of the tree, we don't have to care at all about anything above the first element. misof is evaluating that infinite geometric series just to provide reassurance that, yes, the overall complexity of this recursion really is Theta(n^3), just like the root of the tree. You're right that the real recursion we have here is finite, but misof's point is that it doesn't matter. Even if we overcount and take the recursion to be infinite, we still have just Theta(n^3).

In example 7, again, the recursion is actually a finite geometric progression, but we can ignore the series because we know that the bulk of the work is done in the last term, and the sum of all of the other work is O(the work at the bottom level). What he's doing, then, is noting that if you have an increasing finite geometric progression, you can reverse the order of the terms and have a decreasing finite geometric progression instead, just like in example 6. Thus, if we can compute the last term in the progression, then we have the asymptotic complexity of the entire recursion, and we can ignore all of the other levels.

Is that a little more clear?

(sidenote, when I first read your post, it took me quite a while of scratching my head trying to figure out why you were talking about Gaussian processes...computer science is acronym hell, I tell you... :) )
Re: Question about Computation Complexity (response to post by Quelloquialism) | Reply
Great! Thanks a lot for the explanation Quelloquialism! It is a lot clearer now! This certainly is a neat trick one can use to solve such equations! Good!
RSS