English subtitles

← List Ranking Part4 - Intro to Parallel Programming

Get Embed Code
2 Languages

Showing Revision 4 created 05/24/2016 by Udacity Robot.

  1. Well let's take a look at the dimensions of this table.
  2. Every node participates in every step, so each step takes order of N work,
  3. and we're doubling the hop count on each step, thus there's log of N steps,
  4. so it takes N log N work to construct the entire table.
  5. Note this is more expensive than the serial algorithm which takes linear work, order of N work.
  6. However, the serial algorithm also takes N steps,
  7. whereas, we're finishing N log N steps here.