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 (oldest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Computational Complexity Question about Computation Complexity
 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!
 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... :) )