WEBVTT
00:00:00.012 --> 00:00:02.805
Well let's take a look at the dimensions of this table.
00:00:02.805 --> 00:00:06.974
Every node participates in every step, so each step takes order of N work,
00:00:06.974 --> 00:00:11.148
and we're doubling the hop count on each step, thus there's log of N steps,
00:00:11.148 --> 00:00:14.684
so it takes N log N work to construct the entire table.
00:00:14.684 --> 00:00:19.023
Note this is more expensive than the serial algorithm which takes linear work, order of N work.
00:00:19.023 --> 00:00:21.843
However, the serial algorithm also takes N steps,
00:00:21.843 --> 00:00:24.901
whereas, we're finishing N log N steps here.