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  | 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
 Subject Author Date Question about Computation Complexity pedrosacosta May 27, 2008 at 6:38 PM EDT Re: Question about Computation Complexity misof May 27, 2008 at 7:08 PM EDT Re: Question about Computation Complexity TheGOAT Jun 10, 2010 at 1:32 PM EDT Re: Question about Computation Complexity TheGOAT Jun 19, 2010 at 2:15 PM EDT Re: Question about Computation Complexity TheGOAT Jul 15, 2010 at 10:21 AM EDT Re: Question about Computation Complexity Quelloquialism Jul 15, 2010 at 6:17 PM EDT Re: Question about Computation Complexity TheGOAT Jul 19, 2010 at 9:12 AM EDT