1
23:59:59,500 --> 00:00:06,473
[MUSIC]. 

2
00:00:06,473 --> 00:00:08,827
Welcome back. 
So this time, I want to talk about what 

3
00:00:08,827 --> 00:00:11,901
this term, scalable, means. 
We made the point that working with 

4
00:00:11,901 --> 00:00:15,593
really large data is an important aspect 
of data science and we mentioned the word 

5
00:00:15,593 --> 00:00:20,510
scalability before we haven't talked 
about really what that might mean. 

6
00:00:20,510 --> 00:00:23,084
So a couple different ways to think about 
it that I want to talk about here on this 

7
00:00:23,084 --> 00:00:26,573
slide are, are here. 
So you know, operationally and in the 

8
00:00:26,573 --> 00:00:30,731
past one way to think about this was look 
it needs to work on data that doesn't fit 

9
00:00:30,731 --> 00:00:34,988
in main memory on a single machine. 
Okay. 

10
00:00:34,988 --> 00:00:37,949
You maybe you still have one machine to 
work with but this means that if it can 

11
00:00:37,949 --> 00:00:42,400
you know, you need to be able to bring 
data off of disks in pieces. 

12
00:00:42,400 --> 00:00:45,650
Operate on it and then maybe write it out 
in pieces, okay? 

13
00:00:45,650 --> 00:00:50,139
And so, a bundle of algorithms that could 
work on data in this fashion by bringing 

14
00:00:50,139 --> 00:00:54,293
in data piece by piece to memory, such 
that the memory footprint at any, any 

15
00:00:54,293 --> 00:00:58,776
given point was small. 
this is something the database has 

16
00:00:58,776 --> 00:01:00,829
provided. 
Alright, so you could write a query and 

17
00:01:00,829 --> 00:01:03,602
you knew for sure that it was going to 
finish as long as the data was there on 

18
00:01:03,602 --> 00:01:06,582
disk. 
And you had sort of a minimal amount of 

19
00:01:06,582 --> 00:01:10,679
memory. 
At least, at least to get started. 

20
00:01:10,679 --> 00:01:13,203
Okay. 
But, and I might, I might use the term 

21
00:01:13,203 --> 00:01:17,213
out of core processing here. 
So, out of core means uses the disk to 

22
00:01:17,213 --> 00:01:20,024
operate. 
So, in core means the entire, everything 

23
00:01:20,024 --> 00:01:22,360
you're doing fits entirely in main 
memory. 

24
00:01:22,360 --> 00:01:25,170
Out of core means you sort of need to 
work with the disk appropriately. 

25
00:01:25,170 --> 00:01:29,318
And so databases were, the database 
community were specialists at out of core 

26
00:01:29,318 --> 00:01:34,642
processing of large data sets. 
But increasingly, this notion of 

27
00:01:34,642 --> 00:01:40,792
scalability wasn't really enough, okay. 
And so you saw this pretty acutely with 

28
00:01:40,792 --> 00:01:44,879
websites that were coming online in the 
2000's, where, you know, one big server, 

29
00:01:44,879 --> 00:01:51,377
no matter how big you bought that server. 
You couldn't bring data off of disks fast 

30
00:01:51,377 --> 00:01:56,234
enough to meet all the requests. 
And so had to start being sure that 

31
00:01:56,234 --> 00:02:02,370
things were in memory, and the only to do 
that is start adding more machines, okay. 

32
00:02:02,370 --> 00:02:06,594
And so, increasingly, especially, you 
know, Google is especially is sort of 

33
00:02:06,594 --> 00:02:11,880
known for this, although many of the 
large media companies do this. 

34
00:02:11,880 --> 00:02:15,114
It's scalable really kind of means being 
able to use up to thousands to maybe even 

35
00:02:15,114 --> 00:02:17,980
more tens of thousands of cheap 
computers. 

36
00:02:17,980 --> 00:02:21,300
And, and apply them all to the same 
problem. 

37
00:02:21,300 --> 00:02:29,620
And so we might call this. 
scale out. 

38
00:02:29,620 --> 00:02:33,760
While getting bigger and bigger and 
bigger main memory and more and more 

39
00:02:33,760 --> 00:02:40,422
cores perhaps would be scale up. 
Okay. 

40
00:02:40,422 --> 00:02:45,774
Fine. 
So another way of looking this is may be 

41
00:02:45,774 --> 00:02:48,477
its little more precise is to think 
whether its going to in terms of 

42
00:02:48,477 --> 00:02:51,639
algorithmic complexity that you may or 
may not familiar with been how much 

43
00:02:51,639 --> 00:02:55,005
computer science you take in but then it 
give you just a flavor of what's going on 

44
00:02:55,005 --> 00:02:59,660
here. 
So in the past. 

45
00:03:01,040 --> 00:03:05,780
You might call an algorithm scalable if, 
for, if given n date items, your 

46
00:03:05,780 --> 00:03:11,645
algorithm does no more than n to to the m 
operations on it. 

47
00:03:11,645 --> 00:03:14,720
Okay. 
So this may, it may be 1, in which case 

48
00:03:14,720 --> 00:03:17,385
it's a linear time algorithm, or it may 
be 2, in which case it's a quadratic time 

49
00:03:17,385 --> 00:03:21,550
algorithm, and so on. 
But this was deemed, you know, tractable. 

50
00:03:21,550 --> 00:03:24,878
Right, and so you'd prove properties 
about, you, you would prove that you can 

51
00:03:24,878 --> 00:03:28,206
find in a, a polynomial time algorithm to 
solve some problem and it was sort of 

52
00:03:28,206 --> 00:03:31,586
thought to be scalable or, or assumed, 
you know, well assumed, it was, that was 

53
00:03:31,586 --> 00:03:36,926
the definition of what scalable was. 
Things that were non-polynomial. 

54
00:03:36,926 --> 00:03:41,151
you know that took more than this, for 
example, exponential, we might have n to 

55
00:03:41,151 --> 00:03:45,441
the n or exponential time algorithms, and 
they grew much, much faster, and they 

56
00:03:45,441 --> 00:03:50,963
were, they didn't scale, okay. 
But, you know, this isn't a very tight 

57
00:03:50,963 --> 00:03:56,226
bound on scalability in practice, right. 
A quadratic time algorithm may be sort of 

58
00:03:56,226 --> 00:03:58,896
feasible. 
You start getting into the fourth, and so 

59
00:03:58,896 --> 00:04:01,882
forth. 
It becomes pretty difficult to do for, 

60
00:04:01,882 --> 00:04:05,670
for very large data sets. 
Okay. 

61
00:04:05,670 --> 00:04:09,320
So, now you would say that it really 
can't just be into the m. 

62
00:04:09,320 --> 00:04:12,500
It's gotta be into the m over k. 
Over some, for some pretty large k. 

63
00:04:12,500 --> 00:04:15,209
So you have to have a lot of K being the 
number of computers you can apply to the 

64
00:04:15,209 --> 00:04:18,386
problem. 
And so, you have to call it an algorithm 

65
00:04:18,386 --> 00:04:22,955
that can really exploit this properly. 
Okay, and then one more point that I'm 

66
00:04:22,955 --> 00:04:26,570
going to make now, but we're not going to 
return to in this segment. 

67
00:04:26,570 --> 00:04:29,330
but, but I hope to at the end of the 
course, is that you know, it could be 

68
00:04:29,330 --> 00:04:33,878
that soon even this isn't good enough. 
And for N data items you really should do 

69
00:04:33,878 --> 00:04:38,946
no more than N log in operations. 
And so, the N here means for every, for 

70
00:04:38,946 --> 00:04:41,950
every data item that comes in over the 
wire. 

71
00:04:41,950 --> 00:04:44,700
So, this is, this is applicable to sort 
of streaming applications. 

72
00:04:44,700 --> 00:04:47,980
And the data is coming in so fast, they 
only get one pass at it. 

73
00:04:47,980 --> 00:04:51,070
So, for every operation I have, I'm 
allowed to process that data item. 

74
00:04:51,070 --> 00:04:54,974
And then I'm allowed to put it in some 
sort of a, of an index, and that's this 

75
00:04:54,974 --> 00:04:59,086
log in factor, okay. 
And so, whenever you see log, you should 

76
00:04:59,086 --> 00:05:01,914
think trees. 
So, I'm allowed to take each item, 

77
00:05:01,914 --> 00:05:05,505
inspect it, and work with it, and then 
stick it in some tree dra-, data 

78
00:05:05,505 --> 00:05:09,410
structure. 
But that might be about it. 

79
00:05:09,410 --> 00:05:13,058
Its just too big to make multiple passes 
out, okay and so example this might be 

80
00:05:13,058 --> 00:05:16,706
this Large Synoptic Survey Telescope that 
we, heard about taking sort of 3 

81
00:05:16,706 --> 00:05:21,204
terabytes a night. 
You can't sort of make too many passes on 

82
00:05:21,204 --> 00:05:24,228
this data at, at one time, okay and so 
this whole area we think of is streaming 

83
00:05:24,228 --> 00:05:28,663
data which I guess I have written here 
but I'll write it again. 

84
00:05:28,663 --> 00:05:35,323
And we'll come back to some of the 
techniques for dealing with big data in 

85
00:05:35,323 --> 00:05:43,150
a, in a streaming context. 
Okay, so fine. 

86
00:05:43,150 --> 00:05:45,160
So, two different views of what scalable 
might mean. 

87
00:05:45,160 --> 00:05:48,184
And we're going to talk in this segment 
to give, to give you some examples and 

88
00:05:48,184 --> 00:05:52,660
some intuition for this, can we make use 
of lots of computers. 

89
00:05:52,660 --> 00:05:59,690
and this N over K, okay? 
Alright, so here's a little example 

90
00:05:59,690 --> 00:06:04,160
problem, that's admittedly somewhat over 
simplified. 

91
00:06:04,160 --> 00:06:08,120
So, we want to find all the matching DNA 
sequences. 

92
00:06:08,120 --> 00:06:13,190
Where a set of sequences a short string 
consisting of the letters g, a, t, and c. 

93
00:06:13,190 --> 00:06:15,670
And you're given a short sequence and you 
want to find all the ones that just 

94
00:06:15,670 --> 00:06:19,288
exactly match that. 
Okay, so find me all the sequences that 

95
00:06:19,288 --> 00:06:22,730
are exactly equal to this one you're 
given. 

96
00:06:22,730 --> 00:06:25,930
So how might you do this. 
Well with this little cartoon imagine 

97
00:06:25,930 --> 00:06:29,625
that each of these black lines is a 
sequence. 

98
00:06:29,625 --> 00:06:32,030
Alright so this black line can correspond 
to this sequence and this black line 

99
00:06:32,030 --> 00:06:35,530
corresponds to this sequence and all the 
other black lines are other sequences. 

100
00:06:35,530 --> 00:06:42,314
And you know, think to yourself for a 
minute, propose an algorithm to, to find 

101
00:06:42,314 --> 00:06:49,820
sequences matching your target sequence. 
Okay. 

102
00:06:49,820 --> 00:06:51,700
Well, making no assumptions about the 
data whatsoever. 

103
00:06:51,700 --> 00:06:56,170
It's just given to you as a list. 
One thing you can do, is, use a linear 

104
00:06:56,170 --> 00:07:00,091
search. 
And so we're going to, inspect the first 

105
00:07:00,091 --> 00:07:05,184
item, and we're going to compare it, to 
our target sequence. 

106
00:07:05,184 --> 00:07:09,295
And if they're equal. 
Great we found one, and if they're not 

107
00:07:09,295 --> 00:07:12,890
equal what do you do, we move on on to 
the next one. 

108
00:07:12,890 --> 00:07:16,672
So this is not equal and this, this all 
happens in time equals 0, and then we 

109
00:07:16,672 --> 00:07:21,110
move o to the next one. 
So at time equals one we check for 

110
00:07:21,110 --> 00:07:25,520
equality and if it doesn't match we keep 
moving on, and so on and so on until we 

111
00:07:25,520 --> 00:07:30,550
get to time 17 where we find. 
A match. 

112
00:07:30,550 --> 00:07:32,820
And here I've said contains instead of 
equal. 

113
00:07:32,820 --> 00:07:35,856
I guess I changed the, the meaning here. 
But so, yes, we found a match and we sent 

114
00:07:35,856 --> 00:07:37,850
it to the output. 
Okay. 

115
00:07:37,850 --> 00:07:41,240
So how long does this take, how many 
operations did we do? 

116
00:07:41,240 --> 00:07:44,816
Well, we did 40 records. 
I'm sorry, we were given 40 records in 

117
00:07:44,816 --> 00:07:49,600
this cartoon and we made 40 comparisons. 
And so with in records, and in 

118
00:07:49,600 --> 00:07:53,160
comparisons, we say that the algorithmic 
complexity is order N. 

119
00:07:53,160 --> 00:07:57,314
OK, so this is a linear time algorithm 
for this simple search and retrieval 

120
00:07:57,314 --> 00:08:00,061
task. 
So the question is, can we do any better? 

121
00:08:00,061 --> 00:08:03,463
And if you've, had some experience 
thinking about data structures, taking 

122
00:08:03,463 --> 00:08:07,606
some data structures classes, you should 
be thinking, yes we can. 

123
00:08:09,220 --> 00:08:12,649
So one way to do this is to sort the 
sequences. 

124
00:08:12,649 --> 00:08:16,250
So how does this happen? 
Well, certainly we could still do the 

125
00:08:16,250 --> 00:08:19,967
linear time algorithm and inspect these 
guys one at a time, but we can also do 

126
00:08:19,967 --> 00:08:26,080
something a little bit smarter. 
What if we start in the middle? 

127
00:08:26,080 --> 00:08:30,616
So, we start in the middle and compare 
our target Sequence to the sequence we 

128
00:08:30,616 --> 00:08:36,795
found here and they're not equal. 
But we can see this one that we found is 

129
00:08:36,795 --> 00:08:40,840
less than our target sequence. 
OK. 

130
00:08:40,840 --> 00:08:45,400
So we know the sequence we're on is to 
the left of our target sequence. 

131
00:08:45,400 --> 00:08:47,730
We know the target sequence is to the 
right. 

132
00:08:47,730 --> 00:08:49,700
Right, it must be somewhere in this 
direction. 

133
00:08:49,700 --> 00:08:56,200
So we've just moved the need to check 
half of the data, right, 20 records. 

134
00:08:56,200 --> 00:09:02,895
So now jump to the middle of this guy and 
compare again, and now we see that well, 

135
00:09:02,895 --> 00:09:08,380
boy, we overshot. 
This one is greater than this one. 

136
00:09:08,380 --> 00:09:10,390
We'll once again. 
Let's see. 

137
00:09:10,390 --> 00:09:14,530
Here, we've removed half of these guys, 
on the first step. 

138
00:09:14,530 --> 00:09:17,850
And here, we now, we've removed half of 
these guys. 

139
00:09:17,850 --> 00:09:29,645
And now we know it's in this range. 
Skip to the half again. 

140
00:09:29,645 --> 00:09:32,016
And you compare this one. 
And now it's less than so we're sort of 

141
00:09:32,016 --> 00:09:33,890
bouncing back and forth around our 
target. 

142
00:09:33,890 --> 00:09:43,315
Let's see if I can draw this a little bit 
than I did, cross those out, cross those 

143
00:09:43,315 --> 00:09:48,245
out. 
And now cross these out And so we know 

144
00:09:48,245 --> 00:09:54,427
it's somewhere on this side. 
And in the next step, we find a match. 

145
00:09:54,427 --> 00:09:58,424
Okay. 
And here, if we have multiple copies of 

146
00:09:58,424 --> 00:10:01,767
the same item. 
We know that they'll be, they'll appear 

147
00:10:01,767 --> 00:10:03,677
next to each other. 
So we could just walk through the 

148
00:10:03,677 --> 00:10:06,550
records, gathering up all the ones that 
match if we needed to. 

149
00:10:06,550 --> 00:10:08,550
Okay. 
So how long did this take? 

150
00:10:08,550 --> 00:10:11,970
Well, here, we still had 40 records. 
But we only made four comparisons. 

151
00:10:13,110 --> 00:10:14,616
Right. 
So within records we made login 

152
00:10:14,616 --> 00:10:17,308
comparisons. 
We did, we navigated this, this sort of 

153
00:10:17,308 --> 00:10:20,948
implicit binary tree. 
We did a binary search over this sorted 

154
00:10:20,948 --> 00:10:24,128
data, okay. 
And so this lookup was order login, now 

155
00:10:24,128 --> 00:10:27,668
we did have to sort the data ahead of 
time, and if you have to include that, 

156
00:10:27,668 --> 00:10:32,010
then that's an in login operation. 
And we're not going to intially talk 

157
00:10:32,010 --> 00:10:34,040
about. 
But once you have that sorted data 

158
00:10:34,040 --> 00:10:39,470
available to you, it's now you know, 
really takes a log in operations. 

159
00:10:39,470 --> 00:10:46,850
So this is perhaps far better 
scalability, alright? 

160
00:10:46,850 --> 00:10:49,661
And this is a, this is a good trick. 
And it's such a good trick that it's been 

161
00:10:49,661 --> 00:10:52,623
baked into many systems. 
Especially I'll argue relational 

162
00:10:52,623 --> 00:10:56,000
database, and we made this point before, 
but I want to make it again. 

163
00:10:56,000 --> 00:10:58,394
I said databases are good at these kinds 
of needle in the haystack problems, 

164
00:10:58,394 --> 00:11:00,751
right? 
It's extracting small results from big 

165
00:11:00,751 --> 00:11:04,530
data sets. 
They can transparently provide this sort 

166
00:11:04,530 --> 00:11:07,698
of old style of scalability. 
What I mean by old style of scalability 

167
00:11:07,698 --> 00:11:10,400
is that fits in main memory, as we've 
said a couple of times. 

168
00:11:10,400 --> 00:11:14,450
And your query will always finish 
regardless of the size you main memory. 

169
00:11:14,450 --> 00:11:18,698
In addition, you can it makes an 
excellent sort of index platform, a 

170
00:11:18,698 --> 00:11:23,480
platform for building and using and 
reusing indexes. 

171
00:11:23,480 --> 00:11:26,361
Okay, so, relational databases are good 
at this old style schema building, this 

172
00:11:26,361 --> 00:11:28,812
sort of out of core algorithms and 
they're also good at this old style 

173
00:11:28,812 --> 00:11:32,100
scalability in the sense of finding logs, 
right? 

174
00:11:32,100 --> 00:11:34,710
Finding logarithmic time algorithms. 
Okay. 

175
00:11:34,710 --> 00:11:38,110
So, when the indexes are easily built, 
and automatically used When appropriate, 

176
00:11:38,110 --> 00:11:42,130
and we talked a little bit about this 
during relational databases. 

177
00:11:42,130 --> 00:11:48,210
You can write a single statement CREATE 
INDEX give it a name on a table and a 

178
00:11:48,210 --> 00:11:56,022
column name, and it will sort records 
according to that column. 

179
00:11:56,022 --> 00:11:59,506
You know, the actual data on disk may or 
may not be physically sorted depending on 

180
00:11:59,506 --> 00:12:04,556
uh,the details of, of which system you're 
using in how, how this is working. 

181
00:12:04,556 --> 00:12:07,888
In typically in this statement it would 
not actually moving the physical records 

182
00:12:07,888 --> 00:12:10,926
around but it would build an auxiliary 
index but regardless you get to take 

183
00:12:10,926 --> 00:12:14,870
advantage of this logarithmic time access 
pattern. 

184
00:12:14,870 --> 00:12:17,184
Okay. 
So just by writing this 1 statement in 1 

185
00:12:17,184 --> 00:12:20,495
line of, of code you can create the index 
and take advantage of it. 

186
00:12:20,495 --> 00:12:24,460
Okay, and then every query that comes 
afterward that needs to to use that, that 

187
00:12:24,460 --> 00:12:28,340
would benefit from using that index is 
able to. 

188
00:12:28,340 --> 00:12:32,090
The optimised automatically selects the 
correct index if it's appropriate to use. 

189
00:12:32,090 --> 00:12:35,066
So this is much easier than you sort of 
having to rewrite your code by hand in 

190
00:12:35,066 --> 00:12:39,080
order to either make it out of core. 
Right? 

191
00:12:39,080 --> 00:12:44,310
Or to take advantage of an index, okay. 
So when you're comparing relational 

192
00:12:44,310 --> 00:12:47,730
databases to, say, scripts in R or 
scripts in Python, there's a lot of 

193
00:12:47,730 --> 00:12:51,930
algorithmic work that's already been done 
for you that you're getting for free just 

194
00:12:51,930 --> 00:12:56,843
by turning your problem into a sequel 
statement. 

195
00:12:56,843 --> 00:13:00,253
Fine so you're you know, bind in, bind 
into a lot of code if you can tie one arm 

196
00:13:00,253 --> 00:13:04,200
behind your back and write it as a sequel 
statement. 

197
00:13:04,200 --> 00:13:08,840
It's not just sequel versus, versus a 
much more expressive language like code. 

198
00:13:08,840 --> 00:13:14,410
You're actually getting a lot of benefit 
out of doing [UNKNOWN] okay. 

199
00:13:14,410 --> 00:13:17,690
So let's look at another task Called read 
trimming. 

200
00:13:17,690 --> 00:13:21,395
So here we're given the same set of DNA 
sequences, but instead of searching for 

201
00:13:21,395 --> 00:13:25,157
one particular sequence, we're going to 
trim the final few base pairs from each 

202
00:13:25,157 --> 00:13:28,040
sequence. 
Okay? 

203
00:13:28,040 --> 00:13:31,631
So we're going to trim off a suffix and 
return the data set where each read, read 

204
00:13:31,631 --> 00:13:35,880
is now just a prefix of the, of a former 
read Read, okay. 

205
00:13:35,880 --> 00:13:37,460
So fine. 
So how do we do this. 

206
00:13:37,460 --> 00:13:40,010
On the reason why you need to trim off 
the suffix. 

207
00:13:40,010 --> 00:13:43,979
This actually comes up in practice and 
the reason is that the accuracy of the 

208
00:13:43,979 --> 00:13:48,137
sequencer drops off fairly and properly 
after a certain length of read and 

209
00:13:48,137 --> 00:13:54,206
trimming off the last. 
Several base pairs, from every single 

210
00:13:54,206 --> 00:13:58,160
read is, kind of a pre-processing 
operation. 

211
00:13:58,160 --> 00:14:05,515
OK. 
Fine, so. 

212
00:14:05,515 --> 00:14:09,790
How do we do this? 
Well, we can do the same trick that we 

213
00:14:09,790 --> 00:14:13,262
tried the first time with the search 
task, meaning that we can process each 

214
00:14:13,262 --> 00:14:20,094
record in turn one at a time, all right. 
So at time 0, we can trim off the, suffix 

215
00:14:20,094 --> 00:14:26,572
here and just return to TACCT. 
And in time 1, we can trim off this 

216
00:14:26,572 --> 00:14:31,991
suffix, and so on. 
And at time 17, there's our old friend. 

217
00:14:31,991 --> 00:14:36,011
That begins with GATTA and so on but here 
you know, unlike the search task there's 

218
00:14:36,011 --> 00:14:39,551
no index that's really going to help us 
right we have to touch every single 

219
00:14:39,551 --> 00:14:43,451
record and manipulate it right we have to 
take a prefix from and remove a suffix 

220
00:14:43,451 --> 00:14:47,291
and so the operation is fundamentally 
order in right there's not going to be a 

221
00:14:47,291 --> 00:14:50,951
algorithm that is less than order in 
right you have to atleast touch every 

222
00:14:50,951 --> 00:14:58,560
single record. 
Okay, but can we do any better? 

223
00:14:58,560 --> 00:15:01,588
Well, yeah, right. 
Processing the first task is completely 

224
00:15:01,588 --> 00:15:05,668
independent from processing the the last 
task, which is completely independent 

225
00:15:05,668 --> 00:15:09,508
from processing this task, well, 
actually, saying task, processing the 

226
00:15:09,508 --> 00:15:12,909
record. 
Okay. 

227
00:15:12,909 --> 00:15:16,248
So while there's no index, we can break 
this data set into pieces and process 

228
00:15:16,248 --> 00:15:19,490
each piece independently. 
Okay. 

229
00:15:19,490 --> 00:15:23,195
So imagine we take our single data set 
and break it into these chunks and assign 

230
00:15:23,195 --> 00:15:26,615
each chunk to a different machine or 
maybe a different processor, to be a 

231
00:15:26,615 --> 00:15:31,420
little bit more general. 
Now at times 0 we can process one 

232
00:15:31,420 --> 00:15:35,140
sequence from each chunk all at the same 
time, and at time one we process the 

233
00:15:35,140 --> 00:15:40,565
second sequence from each chunk all at 
the same time, and so on. 

234
00:15:40,565 --> 00:15:44,374
And so here, how much work did we do? 
Well, we did the same amount of work, we 

235
00:15:44,374 --> 00:15:47,400
still process all 40 records. 
But how much time did it take? 

236
00:15:47,400 --> 00:15:50,822
Well it only took seven, I say cycles 
here, s-, seven, time units to be a 

237
00:15:50,822 --> 00:15:55,640
little more general, because we were 
given these six workers. 

238
00:15:55,640 --> 00:15:59,460
And so, the complexity here is n over k, 
right?. 

239
00:15:59,460 --> 00:16:04,047
For every item we can divide by but, we 
do, on average, for any items we do 

240
00:16:04,047 --> 00:16:09,800
[LAUGH] in over k times stands for 
completed the work. 

241
00:16:09,800 --> 00:16:09,890
Okay? 
[BLANK_AUDIO]