 |
Multi-level recursion, number of levels = L |
| | |
|
Branching factor b = exp( log(N)/L ) (Lth root of N) |
| | |
|
First pass cost: O( T * b ) |
| | |
|
Second pass cost per group: O( T/b * b) = O( T ) |
| | |
|
Total second pass cost: O( b * T ) |
| | |
|
Third pass cost per group: O( T/(b*b) * b) = O( T/b ) |
| | |
|
Total third pass cost: O( b*b * T/b ) = O( b * T ) |
| | |
|
Total cost reduction factor: N/(bL) |
