- #1

- 19

- 0

So basically, for a worst case scenario, with infinite recursions, I should have some sum,

[tex] \sum_{i=0}^{\infty} \frac{T}{2^i^{(k-1)}}[/tex]

Where [tex]T[/tex] is a constant. does this look about right?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter homomorphism
- Start date

- #1

- 19

- 0

So basically, for a worst case scenario, with infinite recursions, I should have some sum,

[tex] \sum_{i=0}^{\infty} \frac{T}{2^i^{(k-1)}}[/tex]

Where [tex]T[/tex] is a constant. does this look about right?

- #2

- 19

- 0

bump...

- #3

- 15,393

- 686

does this look about right?

You are doing several things wrong here. You are assuming that the problem at hand can be partitioned. This is not always the case. You are assuming that partitioning buys something, and this also is not always the case. Even if some problem can be partitioned and the partitioned problem is easier to solve, there is typically a cost involved in reconstructing the solution in terms of the original problem. Finally, you are assuming infinite recursion.

Consider a couple of examples: Multiplying a pair of square matrices and sorting a list.

Using conventional matrix multiplication algorithm to compute the product of a pair of NxN matrices requires N

There exists a non-conventional technique for multiplying 2x2 matrices that requires but seven multiplications (but at the cost of extra bookkeeping and a lot of extra additions). Partitioning can be of benefit here. Infinite recursion is not possible; A 1x1 matrix cannot be split into smaller parts. For large matrices, this technique can be used to reduce the order from N

Partitioning is the key tactic needed to make sorting an O(n*log(n)) problem rather than O(n

- #4

- 19

- 0

- #5

- 15,393

- 686

Share:

- Replies
- 1

- Views
- 2K