[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.01,0:00:02.81,Default,,0000,0000,0000,,Well let's take a look at the dimensions of this table.
Dialogue: 0,0:00:02.81,0:00:06.97,Default,,0000,0000,0000,,Every node participates in every step, so each step takes order of N work,
Dialogue: 0,0:00:06.97,0:00:11.15,Default,,0000,0000,0000,,and we're doubling the hop count on each step, thus there's log of N steps,
Dialogue: 0,0:00:11.15,0:00:14.68,Default,,0000,0000,0000,,so it takes N log N work to construct the entire table.
Dialogue: 0,0:00:14.68,0:00:19.02,Default,,0000,0000,0000,,Note this is more expensive than the serial algorithm which takes linear work, order of N work.
Dialogue: 0,0:00:19.02,0:00:21.84,Default,,0000,0000,0000,,However, the serial algorithm also takes N steps,
Dialogue: 0,0:00:21.84,0:00:24.90,Default,,0000,0000,0000,,whereas, we're finishing N log N steps here.