You are not logged in.
- Index
- » Coder's Corner
- » Divide and Conquer Algorithms
Post a reply
Topic review (newest first)
- dannyv
- 2007-09-21 02:58:37
Thanks, know is cristal clear!! :-)
- Ricky
- 2007-09-21 02:23:22
When you have a divide and conquer algorithm, they do something on each step after they divide. O(n^d) is the cost of what they do on this step. So let's say my imaginary algorithm divides a list in half, then sorts each part of that list with bubble sort. The cost of the bubble sort is n^2, so d = 2.
- dannyv
- 2007-09-21 00:50:28
Does anyone read the book "Algorithms" by Papadimitriou et al.? I found it to be an excellent book, just sometime need a little bit of explanation in some parts of it. For example, in chapter 2 about divide and conquer algorithms it presents a master theorem about the time complexity for this kind of algoritms. It saids something like this:
"If T(n)=aT(n/b)+O(n^d) for some constants a>0, b>1 and d>=0 then
T(n)= O(n^d) if d>log_b(a)
T(n)= O(n^d log n) if d=log_b(a)
T(n)= O(n^{log_b(a)}) if d<log_b(a)
Where n is the size of the input, a is the branching factor and b is how much we partition the input in each recursion step."
Can anyone tell me what is the parameter d?
Thanks