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
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
RSS