5,337
edits
Parallel Algorithms: Difference between revisions
→2-3 tree
| Line 238: | Line 238: | ||
** Then insert in parallel <math>(c_1,...,c_{k/2-1}</math> and <math>(c_{k/2+1},...,c_k)</math> | ** Then insert in parallel <math>(c_1,...,c_{k/2-1}</math> and <math>(c_{k/2+1},...,c_k)</math> | ||
** Time is <math>O(\log k \log n)</math> using <math>k</math> processors. | ** Time is <math>O(\log k \log n)</math> using <math>k</math> processors. | ||
===Pipelining=== | |||
* There are <math>\log k</math> waves of the absorb procedure. | |||
* Apply pipelining to make the time <math>O(\log n + \log k)</math> | |||
==Resources== | ==Resources== | ||