Cost comparison

• Computational costs are identical.
• Communication patterns between nodes are very different:
  • Traditional method has two transposition phases in which each node communicates with every other node.
  • New method has $\log_2 n$ phases in which only pairs of nodes communicate.