WEBVTT
1
00:00:00.000 --> 00:00:05.000
In your problem set, I'm going to ask you to prove that the number of scheme programs is countable.
2
00:00:05.000 --> 00:00:07.000
And I'll tell you the hint for that.
3
00:00:07.000 --> 00:00:11.000
Everyone of your scheme programs has a certain number of characters in it, right?
4
00:00:11.000 --> 00:00:16.000
So we can list all the scheme programs by how many characters they have.
5
00:00:16.000 --> 00:00:19.000
All the scheme programs with one character, all the scheme programs with two characters,
6
00:00:19.000 --> 00:00:22.000
all the scheme programs with three characters, right?
7
00:00:22.000 --> 00:00:24.000
So I'm making a list.
8
00:00:24.000 --> 00:00:27.000
So what about the programs say that have a hundred characters?
9
00:00:27.000 --> 00:00:30.000
How should I order them?
10
00:00:30.000 --> 00:00:33.000
Why can't I just do it alphabetically or something?
11
00:00:33.000 --> 00:00:35.000
I mean, it's not so hard to order programs.
12
00:00:35.000 --> 00:00:36.000
You make a list of them.
13
00:00:36.000 --> 00:00:38.000
You make a function that goes down from one to infinity.
14
00:00:38.000 --> 00:00:40.000
But what about the things that programs want to do?
15
00:00:40.000 --> 00:00:43.000
What about functions that programs want to compute?
16
00:00:43.000 --> 00:00:45.000
That's a lot harder.
17
00:00:45.000 --> 00:00:52.000
So what I want to convince you of is that there are more things to compute than there are programs to compute them.
18
00:00:52.000 --> 00:00:58.000
And the idea here is an idea called diagonalization. It was one of the main things that can't or use
19
00:00:58.000 --> 00:01:01.000
to prove that the real numbers are not countable.
20
00:01:01.000 --> 00:01:03.000
And it's going to come up in this example.
21
00:01:03.000 --> 00:01:05.000
And I'll do it real briefly just to give you a sense of it.
22
00:01:05.000 --> 00:01:08.000
And you'll see it again in recitation.
23
00:01:12.000 --> 00:01:15.000
As I just mentioned, you can count all the scheme programs.
24
00:01:15.000 --> 00:01:16.000
You can number them.
25
00:01:16.000 --> 00:01:19.000
This one's number one. This one's number two. This one's number three, right?
26
00:01:19.000 --> 00:01:22.000
In order. And I'm going to number them down here.
27
00:01:25.000 --> 00:01:28.000
Programs.
28
00:01:28.000 --> 00:01:30.000
Okay?
29
00:01:30.000 --> 00:01:37.000
Over here, I'm just going to list the numbers one, two, three, four, five, six, et cetera.
30
00:01:37.000 --> 00:01:40.000
And I'm going to fill in this chart in the following way.
31
00:01:40.000 --> 00:01:45.000
This program number one that we called program number one can work on any input that we put in.
32
00:01:45.000 --> 00:01:49.000
We can put in the number one as input. We can put in the number two as input.
33
00:01:49.000 --> 00:01:52.000
In fact, let's think of these numbers as representing programs again.
34
00:01:52.000 --> 00:01:55.000
So we're putting in programs to this program.
35
00:01:55.000 --> 00:01:59.000
You have a scheme function and you type in a program to it as input.
36
00:01:59.000 --> 00:02:02.000
When it says, you know, please type in your input, you type in program number one.
37
00:02:02.000 --> 00:02:06.000
And your scheme function is going to either say yes or no.
38
00:02:06.000 --> 00:02:10.000
It's either going to stop and say, yes, I like this program or no, I don't like this program.
39
00:02:10.000 --> 00:02:14.000
So these are all the programs that just end up saying yes or no.
40
00:02:14.000 --> 00:02:17.000
They don't do anything clever except saying yes or no to an input.
41
00:02:17.000 --> 00:02:24.000
So let's put in some value. Say it says no to this, yes to this, no to this, no, no, no, et cetera.
42
00:02:24.000 --> 00:02:38.000
And I can fill in this chart with zeros and ones.
43
00:02:38.000 --> 00:02:40.000
Now, there's something a little fishy with what I'm saying.
44
00:02:40.000 --> 00:02:43.000
Can I really fill in this chart?
45
00:02:43.000 --> 00:02:46.000
Why not?
46
00:02:46.000 --> 00:02:49.000
Okay, it goes on forever. That's true.
47
00:02:49.000 --> 00:02:54.000
But I could at least describe filling it in.
48
00:02:54.000 --> 00:02:55.000
Is it even worse than that?
49
00:02:55.000 --> 00:02:57.000
What if I got up to this spot right here?
50
00:02:57.000 --> 00:03:02.000
Program number six, I put in program number one and I wait to see whether it says yes or no.
51
00:03:02.000 --> 00:03:04.000
And I wait. And I wait.
52
00:03:04.000 --> 00:03:06.000
And I wait a little more.
53
00:03:06.000 --> 00:03:09.000
And July, and 80, it was over.
54
00:03:09.000 --> 00:03:13.000
And I go check on how you're all doing. 10 years later down the road.
55
00:03:13.000 --> 00:03:18.000
Everybody's doing fine happily married with lots of kids, making lots of money and doing their dream.
56
00:03:18.000 --> 00:03:20.000
And everybody's just completely content.
57
00:03:20.000 --> 00:03:26.000
And I say, hey, by the way, that program number six is still running on input number one.
58
00:03:26.000 --> 00:03:28.000
I'm still not sure if it says yes or no.
59
00:03:28.000 --> 00:03:31.000
Right? Then we're all dead and it's 10 generations down.
60
00:03:31.000 --> 00:03:33.000
And it's the earth gets destroyed.
61
00:03:33.000 --> 00:03:34.000
There's new civilization.
62
00:03:34.000 --> 00:03:37.000
They find my little program running on a microchip that's sitting there.
63
00:03:37.000 --> 00:03:40.000
And it's still running and running. And this runs forever and ever and ever.
64
00:03:40.000 --> 00:03:43.000
How do I know it's ever going to stop?
65
00:03:43.000 --> 00:03:45.000
We got a wait long enough.
66
00:03:45.000 --> 00:03:47.000
It might never stop.
67
00:03:47.000 --> 00:03:51.000
So it's possible that one of these things, you know, I might not be able to fill in.
68
00:03:51.000 --> 00:03:58.000
But for the purposes of this argument, let's just say that, look, if it accepts it, I'll put a one in.
69
00:03:58.000 --> 00:04:00.000
And if it doesn't, there's a zero.
70
00:04:00.000 --> 00:04:01.000
And I might not know that.
71
00:04:01.000 --> 00:04:04.000
But here's what I could do to conceivably fill in this chart.
72
00:04:04.000 --> 00:04:07.000
I could run each one of these programs for one step.
73
00:04:07.000 --> 00:04:12.000
And then I could run the second one for two steps.
74
00:04:12.000 --> 00:04:14.000
And then the first one for an additional step.
75
00:04:14.000 --> 00:04:16.000
Then I'll start the third one. I'll run this for one step.
76
00:04:16.000 --> 00:04:18.000
Then I'll run this for another step.
77
00:04:18.000 --> 00:04:22.000
I could run them all at the same time, adding one step each time.
78
00:04:22.000 --> 00:04:27.000
So that's sooner or later, if the thing had a one in there, I could fill it in.
79
00:04:27.000 --> 00:04:31.000
In other words, I wouldn't get stuck at one program waiting and waiting and not be able to fill in the rest of the table.
80
00:04:31.000 --> 00:04:35.000
I would do one step at this program and then add an extra step to all the others I had done.
81
00:04:35.000 --> 00:04:37.000
And then start with the next one.
82
00:04:37.000 --> 00:04:40.000
So that's sooner or later, if it's going to stop and say, yes, I'll be able to put a one.
83
00:04:40.000 --> 00:04:43.000
And if it's going to run forever, it'll never put anything in there.
84
00:04:43.000 --> 00:04:46.000
But I want to have to worry about us getting stuck along the way.
85
00:04:46.000 --> 00:04:48.000
So I don't understand that trick.
86
00:04:48.000 --> 00:04:50.000
That's sometimes called dovetailing.
87
00:04:50.000 --> 00:04:53.000
It's a trick to get all these things to run at the same time.
88
00:04:53.000 --> 00:04:58.000
So I could convince you that conceivably, I'll put all the ones in at some point.
89
00:04:58.000 --> 00:05:04.000
So you're saying that program 6 and position 7 is an infinite loop to it?
90
00:05:04.000 --> 00:05:08.000
Say program 6 on input 1 has an infinite loop.
91
00:05:08.000 --> 00:05:13.000
And I don't want it to get stuck there because then I couldn't convince you that I can.
92
00:05:13.000 --> 00:05:15.000
So here's what I do.
93
00:05:15.000 --> 00:05:18.000
I run program 1 for one step on this input.
94
00:05:18.000 --> 00:05:19.000
Okay.
95
00:05:19.000 --> 00:05:24.000
And then I run program 2 for 2 and then 1 for an additional one.
96
00:05:24.000 --> 00:05:29.000
I run program 1 for this one on one step.
97
00:05:29.000 --> 00:05:31.000
Then I run program 2 for this one.
98
00:05:31.000 --> 00:05:33.000
Then I run program 3 for this one.
99
00:05:33.000 --> 00:05:36.000
And every step along, I add one step for each of these programs.
100
00:05:36.000 --> 00:05:38.000
What happens when you hit 6?
101
00:05:38.000 --> 00:05:41.000
I do one step of that program.
102
00:05:41.000 --> 00:05:45.000
And then I do one more step for each of these on all of these inputs.
103
00:05:45.000 --> 00:05:47.000
And then I continue with program 7.
104
00:05:47.000 --> 00:05:48.000
Right.
105
00:05:48.000 --> 00:05:49.000
I leave it as a question mark.
106
00:05:49.000 --> 00:05:52.000
And these things eventually get filled in when we need to fold them in.
107
00:05:52.000 --> 00:05:54.000
All right.
108
00:05:54.000 --> 00:05:55.000
I don't want to spend too much time.
109
00:05:55.000 --> 00:05:57.000
This is actually a subject and theory of computation.
110
00:05:57.000 --> 00:05:59.000
But I want you to see this one idea of diagonalization.
111
00:05:59.000 --> 00:06:00.000
Now let's say I've done this.
112
00:06:00.000 --> 00:06:02.000
I now have this big chart filled in.
113
00:06:02.000 --> 00:06:03.000
Okay.
114
00:06:03.000 --> 00:06:04.000
I have all these programs listed here.
115
00:06:04.000 --> 00:06:06.000
Every single program in the whole world listed here.
116
00:06:06.000 --> 00:06:07.000
Okay.
117
00:06:07.000 --> 00:06:08.000
I have all the inputs listed here.
118
00:06:08.000 --> 00:06:12.000
And I have, look at these things.
119
00:06:12.000 --> 00:06:17.000
A particular row here represents a computation.
120
00:06:17.000 --> 00:06:21.000
It represents a list of programs that this program accepts.
121
00:06:21.000 --> 00:06:23.000
An elicit that it doesn't accept.
122
00:06:23.000 --> 00:06:26.000
In particular, a list that it accepts.
123
00:06:26.000 --> 00:06:36.000
I want to convince you that there is a list of acceptance that isn't in this table.
124
00:06:36.000 --> 00:06:42.000
In other words, there's a computation like this that none of my programs are doing.
125
00:06:42.000 --> 00:06:43.000
Okay.
126
00:06:43.000 --> 00:06:46.000
Each one of these infinite sequences of zeros and ones represents a computation.
127
00:06:46.000 --> 00:06:49.000
Represent something that you might want to write a program to do.
128
00:06:49.000 --> 00:06:52.000
I'm going to convince you that after you've listed all your programs down,
129
00:06:52.000 --> 00:06:58.000
and I filled in this chart, there is a particular computation, a sequence of zeros and ones,
130
00:06:58.000 --> 00:07:02.000
accepting or rejecting these inputs that doesn't exist in this table.
131
00:07:02.000 --> 00:07:05.000
All your programs are unique.
132
00:07:05.000 --> 00:07:07.000
All my programs are unique.
133
00:07:07.000 --> 00:07:08.000
Yeah.
134
00:07:08.000 --> 00:07:10.000
But even if they weren't, it would be okay.
135
00:07:10.000 --> 00:07:12.000
I mean, I could have two that have the same computation.
136
00:07:12.000 --> 00:07:15.000
I'm going to convince you there's a new one that's different from all the ones in my list.
137
00:07:15.000 --> 00:07:17.000
I know how it works.
138
00:07:17.000 --> 00:07:21.000
Right. I don't think I need to say that these are unique.
139
00:07:21.000 --> 00:07:24.000
Even if they're the same, it's okay, I think.
140
00:07:24.000 --> 00:07:25.000
So here's what I'm going to do.
141
00:07:25.000 --> 00:07:29.000
I'm going to go down...
142
00:07:29.000 --> 00:07:32.000
I'm going to go down this diagonal. That's why it's called diagonalization.
143
00:07:32.000 --> 00:07:35.000
And I'm going to create a new set of zeros and ones.
144
00:07:35.000 --> 00:07:39.000
And I'm going to convince you that that set of zeros and ones doesn't exist in my table anyplace.
145
00:07:39.000 --> 00:07:43.000
That means there's a computation and none of my programs compute it.
146
00:07:43.000 --> 00:07:48.000
That means there's a program that's missing from my list.
147
00:07:48.000 --> 00:07:51.000
In other words, there's a computation and there's no program that does it.
148
00:07:51.000 --> 00:07:53.000
Here's how I'm going to do it.
149
00:07:53.000 --> 00:07:55.000
Every place I see a zero, I change it to a one.
150
00:07:55.000 --> 00:07:58.000
Every place I see a one, I change it to a zero.
151
00:07:58.000 --> 00:08:01.000
What happens if you hit a question mark?
152
00:08:01.000 --> 00:08:06.000
Zeroes or question marks change to...
153
00:08:06.000 --> 00:08:07.000
You have...
154
00:08:07.000 --> 00:08:08.000
Change to ones.
155
00:08:08.000 --> 00:08:10.000
One's changed to zeros.
156
00:08:10.000 --> 00:08:12.000
You have scattered questions mark.
157
00:08:12.000 --> 00:08:15.000
You have scattered question marks, right?
158
00:08:15.000 --> 00:08:21.000
Yeah, I think we'll have to turn question marks into ones.
159
00:08:21.000 --> 00:08:25.000
Zeroes and question marks will turn into ones and ones will turn into zeros.
160
00:08:25.000 --> 00:08:27.000
Is there?
161
00:08:27.000 --> 00:08:30.000
Yeah, if you announce that a question mark is a one, then...
162
00:08:30.000 --> 00:08:33.000
...the guy goes with a zero there.
163
00:08:33.000 --> 00:08:36.000
Oh, yeah.
164
00:08:36.000 --> 00:08:38.000
Right, right. It might go back the other way.
165
00:08:38.000 --> 00:08:39.000
Right? It's true.
166
00:08:39.000 --> 00:08:46.000
Yeah, I'm trying to avoid technicalities and I'm getting more technicalities.
167
00:08:46.000 --> 00:08:47.000
All right.
168
00:08:47.000 --> 00:08:51.000
I can't fix that easily without changing the way I want to do this.
169
00:08:51.000 --> 00:08:54.000
So let's say no question marks.
170
00:08:54.000 --> 00:08:56.000
Yeah. Let's say no question.
171
00:08:56.000 --> 00:08:58.000
Let's say these are all say zeroes or ones.
172
00:08:58.000 --> 00:09:02.000
It's not so realistic, but at least you'll get the notion.
173
00:09:02.000 --> 00:09:05.000
If I go down this diagonal and I change zeros to ones and the ones to zeros,
174
00:09:05.000 --> 00:09:07.000
then I get a new list of ones and zeros.
175
00:09:07.000 --> 00:09:10.000
And that new list...
176
00:09:10.000 --> 00:09:11.000
Here, let's write it in.
177
00:09:11.000 --> 00:09:15.000
It's one, zero, zero, zero, and then it would keep going.
178
00:09:15.000 --> 00:09:20.000
This list is different from this one.
179
00:09:20.000 --> 00:09:22.000
It's different from this one.
180
00:09:22.000 --> 00:09:23.000
It's different from this one.
181
00:09:23.000 --> 00:09:28.000
It's different from all the ones in this long infinite list of programs.
182
00:09:28.000 --> 00:09:30.000
That means...
183
00:09:30.000 --> 00:09:33.000
Can you present that to me?
184
00:09:33.000 --> 00:09:36.000
Yeah, I guess you... well, you don't need to really, but you could.
185
00:09:36.000 --> 00:09:39.000
In other words, it's a list of zeros and ones that isn't in there yet,
186
00:09:39.000 --> 00:09:44.000
which means that there's some computation that exists,
187
00:09:44.000 --> 00:09:47.000
and there's no program that does it.
188
00:09:47.000 --> 00:09:48.000
Yeah.
189
00:09:48.000 --> 00:09:52.000
I've seen this before and I understand how you generate the new number.
190
00:09:52.000 --> 00:09:57.000
But I'm never really sure how we know if we have an infinite list.
191
00:09:57.000 --> 00:10:01.000
But that is a unique value that we just drew in there.
192
00:10:01.000 --> 00:10:05.000
Because this value has got to be different than every one of the ones that's already there.
193
00:10:05.000 --> 00:10:09.000
Different than the ones in the diagonal, but what about ones that work?
194
00:10:09.000 --> 00:10:12.000
In row 29.
195
00:10:12.000 --> 00:10:16.000
In row 29, it'll differ from the 29th row in the 29th spot.
196
00:10:16.000 --> 00:10:17.000
Okay.
197
00:10:17.000 --> 00:10:20.000
It'll differ from row 152 in the 150th second spot.
198
00:10:20.000 --> 00:10:22.000
Right. Right.
199
00:10:22.000 --> 00:10:25.000
So it's going to be different from all the other computations that's there,
200
00:10:25.000 --> 00:10:29.000
and therefore there's a program that doesn't exist.
201
00:10:29.000 --> 00:10:31.000
Anyway, the main idea I want you to get here,
202
00:10:31.000 --> 00:10:35.000
you'll see this in more detail in a more rigorous way in recitation.
203
00:10:35.000 --> 00:10:38.000
But what I want you to get the sense is that this idea of the diagonalization
204
00:10:38.000 --> 00:10:40.000
does connect back to programs.
205
00:10:40.000 --> 00:10:43.000
And it's not just a completely abstract idea.
206
00:10:43.000 --> 00:10:46.000
And you'll see it again in more detail in theory of computation.
207
00:10:46.000 --> 00:10:50.000
The conclusion is that there are things that you want to compute
208
00:10:50.000 --> 00:10:52.000
that there are no programs for.
209
00:10:52.000 --> 00:10:54.000
That if you try to list all the programs,
210
00:10:54.000 --> 00:10:58.000
and you think you have them all listed and numbered from one down to infinity,
211
00:10:58.000 --> 00:11:03.000
that there's some computation that could be defined,
212
00:11:03.000 --> 00:11:06.000
and there's no program that connects to that computation.
213
00:11:06.000 --> 00:11:09.000
That there are more things to compute than there are programs.
214
00:11:09.000 --> 00:11:11.000
That's a good way of putting it.
215
00:11:11.000 --> 00:11:16.000
And by the order of infinity is greater than the number of integers.
216
00:11:16.000 --> 00:11:25.000
There's more computable functions than there are integers, than there are programs.
217
00:11:25.000 --> 00:11:28.000
There's more things to compute than there are programs.
218
00:11:28.000 --> 00:11:33.000
Are you allowing programs to have data listed within them such as a program,
219
00:11:33.000 --> 00:11:37.000
which for example, multiplies any input by two?
220
00:11:37.000 --> 00:11:39.000
Yeah, yeah, include anything like that, right?
221
00:11:39.000 --> 00:11:41.000
Uh-oh, you mean things that don't just say yes or no?
222
00:11:41.000 --> 00:11:42.000
What do you mean?
223
00:11:42.000 --> 00:11:44.000
Yeah, it's only me.
224
00:11:44.000 --> 00:11:46.000
I'm not quite sure what you mean by program.
225
00:11:46.000 --> 00:11:49.000
Here we're talking programs that do very simple things.
226
00:11:49.000 --> 00:11:54.000
Programs that take an input and tell you yes or no on the input.
227
00:11:54.000 --> 00:11:57.000
But that's an even smaller set than programs in general.
228
00:11:57.000 --> 00:12:04.000
And you can still do the same thing and just change each of the outputs by something.
229
00:12:04.000 --> 00:12:07.000
Right, you can make a program without putting it into something with the s or no.
230
00:12:07.000 --> 00:12:09.000
You could do that.
231
00:12:09.000 --> 00:12:15.000
All right, I should say, I promised at the beginning that I would try to do lecture notes for all these things.
232
00:12:15.000 --> 00:12:18.000
And I do have new lecture notes that I printed out,
233
00:12:18.000 --> 00:12:20.000
and you can look up these things.
234
00:12:20.000 --> 00:12:25.000
And hopefully I will keep up to date here if I have time to always give you guys stuff.
235
00:12:25.000 --> 00:12:28.000
You don't have to scribble while I talk.
236
00:12:28.000 --> 00:12:40.000
Okay, this is a topic which you'll see again and again.
237
00:12:40.000 --> 00:12:45.000
Maybe the most common thing you'll see for the rest of the semesters.
238
00:12:45.000 --> 00:12:47.000
You'll see it in Java, you'll see it in algorithm.
239
00:12:47.000 --> 00:12:52.000
This is a topic that talks about how to measure how fast functions are growing.
240
00:12:52.000 --> 00:12:54.000
And it's fundamental in algorithms.
241
00:12:54.000 --> 00:12:59.000
In the very, very early days of algorithms, somebody would come up with an algorithm to do something.
242
00:12:59.000 --> 00:13:02.000
They publish a paper, they do some experiments, they print the results,
243
00:13:02.000 --> 00:13:04.000
kind of like an laboratory setting.
244
00:13:04.000 --> 00:13:07.000
They'd say, I ran it on this computer, on this kind of input,
245
00:13:07.000 --> 00:13:09.000
and here's how many milliseconds it took.
246
00:13:09.000 --> 00:13:13.000
And it's hard to make a comparison between that and somebody else's paper.
247
00:13:13.000 --> 00:13:17.000
If they ran it on a different machine or they had a different compiler,
248
00:13:17.000 --> 00:13:20.000
or they had a different implementation, or they used a different programming language.
249
00:13:20.000 --> 00:13:25.000
So soon after that, the theory kind of came up to give a solid foundation.
250
00:13:25.000 --> 00:13:31.000
And we compare algorithms not by just experimenting and looking at the actual number of milliseconds,
251
00:13:31.000 --> 00:13:35.000
but by somehow looking at the algorithm itself and saying this takes a certain amount of time
252
00:13:35.000 --> 00:13:38.000
in the pendant of the underlying implementation.
253
00:13:38.000 --> 00:13:41.000
And we compare algorithms based on that criterion.
254
00:13:41.000 --> 00:13:44.000
And that's what this theory is all about.
255
00:13:44.000 --> 00:13:47.000
It's about trying to get a metric for how fast functions are growing.
256
00:13:47.000 --> 00:13:56.000
And those functions are typically coming from how long a particular algorithm is taking.
257
00:13:56.000 --> 00:14:11.000
Alright, so let's do an example.
258
00:14:11.000 --> 00:14:17.000
We're going to do a very, very well-known sorting program called bubble sort for a second.
259
00:14:17.000 --> 00:14:19.000
We're going to calculate how many steps this takes.
260
00:14:19.000 --> 00:14:21.000
Here's how the program works.
261
00:14:21.000 --> 00:14:24.000
You put a bunch of numbers up like this on a list.
262
00:14:24.000 --> 00:14:27.000
And you compare the first two things on a list.
263
00:14:27.000 --> 00:14:31.000
And if you'd like to make this an ascending order from smallest to highest.
264
00:14:31.000 --> 00:14:39.000
So if the first one is bigger, then the second one, you want to switch their locations.
265
00:14:39.000 --> 00:14:44.000
So in this case, that becomes 6 and then 8.
266
00:14:44.000 --> 00:14:48.000
And then you continue going down to the next pair, 8 and 2.
267
00:14:48.000 --> 00:14:51.000
So you get 2, 8.
268
00:14:51.000 --> 00:14:55.000
8 and 10.
269
00:14:55.000 --> 00:14:57.000
10 and 5.
270
00:14:57.000 --> 00:15:00.000
5, 10.
271
00:15:00.000 --> 00:15:02.000
That's called one bubble procedure.
272
00:15:02.000 --> 00:15:04.000
It doesn't sort the list yet.
273
00:15:04.000 --> 00:15:07.000
What do we have to do to sort the list?
274
00:15:07.000 --> 00:15:08.000
Right, we have to do it again.
275
00:15:08.000 --> 00:15:11.000
So if we did it again, what would happen?
276
00:15:11.000 --> 00:15:12.000
2, 6.
277
00:15:12.000 --> 00:15:14.000
5.
278
00:15:14.000 --> 00:15:17.000
I'm going to do the whole thing.
279
00:15:17.000 --> 00:15:19.000
8, 10.
280
00:15:19.000 --> 00:15:21.000
OK, now we have to do it one more time.
281
00:15:21.000 --> 00:15:22.000
It looks like.
282
00:15:22.000 --> 00:15:25.000
2, 5, 6, 8, 10.
283
00:15:25.000 --> 00:15:30.000
All right, let's analyze how much time this takes.
284
00:15:30.000 --> 00:15:32.000
How many steps does this first bubble procedure take?
285
00:15:32.000 --> 00:15:36.000
Let's say comparing are the things we're counting up.
286
00:15:36.000 --> 00:15:37.000
How many comparisons?
287
00:15:37.000 --> 00:15:39.000
One comparison here.
288
00:15:39.000 --> 00:15:40.000
One here.
289
00:15:40.000 --> 00:15:41.000
One here.
290
00:15:41.000 --> 00:15:42.000
One here.
291
00:15:42.000 --> 00:15:43.000
One here.
292
00:15:43.000 --> 00:15:46.000
If there's n numbers, then it's n minus 1.
293
00:15:46.000 --> 00:15:48.000
How much does the next one take?
294
00:15:48.000 --> 00:15:49.000
In the worst case.
295
00:15:49.000 --> 00:15:50.000
2.
296
00:15:50.000 --> 00:15:54.000
How come only n minus 2, not n minus 1?
297
00:15:54.000 --> 00:15:57.000
Because this 10, what do you know about it?
298
00:15:57.000 --> 00:15:59.000
It's definitely the biggest number.
299
00:15:59.000 --> 00:16:01.000
When you're finished with a bubble procedure,
300
00:16:01.000 --> 00:16:04.000
you can prove that the biggest number is sitting at the bottom.
301
00:16:04.000 --> 00:16:10.000
And the other number is bubble, so to speak, upwards in some less predictable way.
302
00:16:10.000 --> 00:16:12.000
But the heaviest one sinks to the bottom.
303
00:16:12.000 --> 00:16:16.000
Therefore, when you go next time, you never have to compare this one to this one anymore.
304
00:16:16.000 --> 00:16:18.000
That's a wasted comparison.
305
00:16:18.000 --> 00:16:22.000
So on the way down here, we do at most n minus 2 comparisons.
306
00:16:22.000 --> 00:16:23.000
And where is this going?
307
00:16:23.000 --> 00:16:31.000
This is the triangle numbers again.
308
00:16:31.000 --> 00:16:33.000
Why do I spend so much time in them?
309
00:16:33.000 --> 00:16:36.000
Because they come up all the time from algorithms as well.
310
00:16:36.000 --> 00:16:41.000
This is an algorithm that takes time proportional to 1 plus 2 plus 3 all the way up to n minus 1,
311
00:16:41.000 --> 00:16:48.000
which you know equals n times divided by 2.
312
00:16:48.000 --> 00:16:51.000
That's the complexity of this algorithm.
313
00:16:51.000 --> 00:16:58.000
This bubble-sort algorithm.
314
00:16:58.000 --> 00:17:07.000
It's not too hard to analyze this algorithm, but now we want to get a sense of what the overall time complexity of this algorithm is.
315
00:17:07.000 --> 00:17:11.000
We like to give it some kind of categorical value.
316
00:17:11.000 --> 00:17:15.000
In this case, the categorical value is going to be this is about n squared.
317
00:17:15.000 --> 00:17:23.000
The about n squared is the part that I'm going to formulate and formalize in these definitions that are coming up.
318
00:17:23.000 --> 00:17:29.000
Are there questions about this so far?
319
00:17:29.000 --> 00:17:32.000
This is the worst case.
320
00:17:32.000 --> 00:17:37.000
This is worst case.
321
00:17:37.000 --> 00:17:41.000
Although if we did the time for flip-flopping, it would double this.
322
00:17:41.000 --> 00:17:50.000
And the idea of this formalization, it's a good question, Doug, is that doubling or quadrupling or any constant change will affect our category of this algorithm.
323
00:17:50.000 --> 00:17:52.000
It would be in the same category.
324
00:17:52.000 --> 00:17:53.000
Questions about this?
325
00:17:53.000 --> 00:18:06.000
I think that's a number of random numbers of sorts.
326
00:18:06.000 --> 00:18:09.000
How many bubble procedures we actually have to do?
327
00:18:09.000 --> 00:18:14.000
Since every time we do one, the correct number sinks to the bottom.
328
00:18:14.000 --> 00:18:21.000
One, two, three, four, and minus one. Right.
329
00:18:21.000 --> 00:18:25.000
Sometimes it gets done earlier and you can put a flag in and say stop.
330
00:18:25.000 --> 00:18:30.000
If the last one didn't change anything, that's right.
331
00:18:30.000 --> 00:18:33.000
Other questions?
332
00:18:33.000 --> 00:18:36.000
Okay.
333
00:18:36.000 --> 00:18:41.000
Here's a very, very dull definition, but we'll do some examples and bring some life to it.
334
00:18:41.000 --> 00:18:49.000
We say that a function is big, oh, another function.
335
00:18:49.000 --> 00:18:56.000
If and only if there exists a C and some number such that
336
00:18:56.000 --> 00:19:06.000
this is in the notes and in your book, you don't have to write it down.
337
00:19:06.000 --> 00:19:15.000
Just look at it and then we'll think about it.
338
00:19:15.000 --> 00:19:18.000
I'll read this off, but then I'll explain what it means in reality.
339
00:19:18.000 --> 00:19:21.000
F of x is big O of g of x.
340
00:19:21.000 --> 00:19:24.000
We say that one function is bounded above by another.
341
00:19:24.000 --> 00:19:29.000
This function is an upper bound for x. It bounds it on top.
342
00:19:29.000 --> 00:19:36.000
If, basically, there's some constant, some fixed number times the g,
343
00:19:36.000 --> 00:19:40.000
which is always bigger than the f.
344
00:19:40.000 --> 00:19:46.000
As long as you're past a certain point, as long as you're past x sub zero.
345
00:19:46.000 --> 00:19:49.000
Now, this is completely obscure if you see it for the first time.
346
00:19:49.000 --> 00:19:52.000
So let me give you an example from what we just did.
347
00:19:52.000 --> 00:19:54.000
Here's a function.
348
00:19:54.000 --> 00:19:59.000
Here's our f function.
349
00:19:59.000 --> 00:20:06.000
f of n equals n squared over 2 minus n over 2.
350
00:20:06.000 --> 00:20:14.000
And I want to convince you that this function, that f of n, is order n squared.
351
00:20:14.000 --> 00:20:18.000
That it's bounded above by n squared.
352
00:20:18.000 --> 00:20:22.000
According to the definition, the way to do this is you have to find a constant
353
00:20:22.000 --> 00:20:28.000
so that the function you're interested in is smaller than that constant times n squared.
354
00:20:28.000 --> 00:20:35.000
You want to show that n squared over 2 minus n over 2 is smaller than or equal to some constant times n squared.
355
00:20:35.000 --> 00:20:38.000
What constant can I use to get this tour?
356
00:20:38.000 --> 00:20:41.000
One.
357
00:20:41.000 --> 00:20:47.000
This is always less than n squared because this is half n squared and this takes away things from it.
358
00:20:47.000 --> 00:20:55.000
So it's completely straightforward that this function is order n squared because one times n squared is bigger than this for every single
359
00:20:55.000 --> 00:20:58.000
n in the whole world and bigger than zero.
360
00:20:58.000 --> 00:21:06.000
So the x zero here would be zero, anything bigger than zero, and the c would be one.
361
00:21:06.000 --> 00:21:13.000
If you want to go through these definitions and show that something is order something else, you have to find the c and find the x zero.
362
00:21:13.000 --> 00:21:20.000
With the theta notation, we have both upper and lower bounds, but this looks like we've only got an upper bound here.
363
00:21:20.000 --> 00:21:22.000
So we could say that...
364
00:21:22.000 --> 00:21:24.000
Yeah, when did we do theta notation?
365
00:21:24.000 --> 00:21:27.000
Well, you did this thing already.
366
00:21:27.000 --> 00:21:29.000
So here's the next step.
367
00:21:29.000 --> 00:21:36.000
All right, so I'm going to zoom along and you're all thinking, oh, we're just getting it, don't zoom along.
368
00:21:36.000 --> 00:21:40.000
Whether you got this last month or not, I don't know how much they did on this, but this is an upper bound.
369
00:21:40.000 --> 00:21:46.000
There's very, very same definition, looks like this, but this is reversed.
370
00:21:46.000 --> 00:21:49.000
So that means omega is a lower bound.
371
00:21:49.000 --> 00:21:51.000
It means it's at least as big.
372
00:21:51.000 --> 00:21:54.000
And if it's both this and this, we say it's big theta.
373
00:21:54.000 --> 00:22:00.000
So it really means to be in the category, that it's bounded above by n squared and it's bounded below by n squared.
374
00:22:00.000 --> 00:22:03.000
If it's both of these, we'd say it's big theta.
375
00:22:03.000 --> 00:22:32.000
Let me convince you now that this one is not only big o n squared, but it's also omega n squared.
376
00:22:32.000 --> 00:22:41.000
This is what we have to do.
377
00:22:41.000 --> 00:22:50.000
For me to show you that this is omega n squared, I have to show you that this function is bigger than something times n squared for all n past a certain point.
378
00:22:50.000 --> 00:22:55.000
Well, it's not going to be bigger than one times n squared because it was less than one times n squared.
379
00:22:55.000 --> 00:22:59.000
So to show that it's bigger than something times n squared, you better use a smaller number than one.
380
00:22:59.000 --> 00:23:02.000
So what number is going to work there?
381
00:23:02.000 --> 00:23:05.000
Probably, 117th work.
382
00:23:05.000 --> 00:23:11.000
How do you know 117th work besides if you're a 17 lover?
383
00:23:11.000 --> 00:23:14.000
What number really works? That's easy to see.
384
00:23:14.000 --> 00:23:15.000
A third.
385
00:23:15.000 --> 00:23:19.000
A third does a half work?
386
00:23:19.000 --> 00:23:20.000
No.
387
00:23:20.000 --> 00:23:22.000
It doesn't, right?
388
00:23:22.000 --> 00:23:27.000
Because a half n squared is going to be bigger than a half n squared minus something.
389
00:23:27.000 --> 00:23:35.000
So Sam just says, well, let's take something that's smaller than that.
390
00:23:35.000 --> 00:23:36.000
Is this true?
391
00:23:36.000 --> 00:23:38.000
Or larger than n, yes.
392
00:23:38.000 --> 00:23:42.000
Could you figure out whether this is true or not? And how would you figure it out?
393
00:23:42.000 --> 00:23:45.000
We're only worried with large n.
394
00:23:45.000 --> 00:23:49.000
We're worried to make sure this is true as soon as n is bigger than a certain number.
395
00:23:49.000 --> 00:23:52.000
And you can tell me what that number is. That's the x0.
396
00:23:52.000 --> 00:23:58.000
As long as it's going to be true past a certain point, this is okay.
397
00:23:58.000 --> 00:23:59.000
What can't be zero?
398
00:23:59.000 --> 00:24:00.000
The constant.
399
00:24:00.000 --> 00:24:04.000
The constant can't be zero. The constant has to be bigger than zero, yeah.
400
00:24:04.000 --> 00:24:06.000
Oh, it would be zero.
401
00:24:06.000 --> 00:24:09.000
You're not going to get a large space.
402
00:24:09.000 --> 00:24:12.000
It's just going to be large.
403
00:24:12.000 --> 00:24:17.000
Right. That's true.
404
00:24:17.000 --> 00:24:20.000
Does the constant have to be positive?
405
00:24:20.000 --> 00:24:23.000
In these definitions, we always use a positive constant.
406
00:24:23.000 --> 00:24:25.000
Yeah.
407
00:24:25.000 --> 00:24:29.000
All right. So how do you figure out what n is going to work here?
408
00:24:29.000 --> 00:24:31.000
You can do some algebra here, right?
409
00:24:31.000 --> 00:24:38.000
You can go ahead and manipulate this around until you have something n greater than or equal to a number.
410
00:24:38.000 --> 00:24:39.000
Should we do it?
411
00:24:39.000 --> 00:24:40.000
Let's do one.
412
00:24:40.000 --> 00:24:45.000
Okay. So how do we manipulate this to figure out this is true for all n greater than something?
413
00:24:45.000 --> 00:24:51.000
I'm going to do the whole third n squared over the left.
414
00:24:51.000 --> 00:24:54.000
All right. So I get.
415
00:24:54.000 --> 00:24:56.000
Okay. Everyone see what I did?
416
00:24:56.000 --> 00:24:58.000
We subtracted a third n squared.
417
00:24:58.000 --> 00:25:03.000
And a half n squared minus a third n squared is a sixth n squared.
418
00:25:03.000 --> 00:25:16.000
The n squared minus a equals to a new zero.
419
00:25:16.000 --> 00:25:20.000
The n squared minus a equals to a new zero.
420
00:25:20.000 --> 00:25:24.000
Okay. As long as n is bigger than or equal to three,
421
00:25:24.000 --> 00:25:28.000
this is all going to be true.
422
00:25:28.000 --> 00:25:32.000
You can always find that number that it's going to be true past that by manipulating this algebraically,
423
00:25:32.000 --> 00:25:35.000
once you guess a constant that actually works.
424
00:25:35.000 --> 00:25:39.000
And depending on the constant you guess, this number may be bigger or smaller.
425
00:25:39.000 --> 00:25:45.000
And you can calculate it. They come in pairs, the constant and the value after which it starts being bigger than.
426
00:25:45.000 --> 00:25:46.000
Okay.
427
00:25:46.000 --> 00:25:50.000
Just a little review before we state this general theorem, Sam just said.
428
00:25:50.000 --> 00:25:54.000
Who wants to try this?
429
00:25:54.000 --> 00:26:00.000
Let's see. I'll help.
430
00:26:00.000 --> 00:26:03.000
Tony, you want to do it?
431
00:26:03.000 --> 00:26:04.000
I'll help you.
432
00:26:04.000 --> 00:26:07.000
We're trying to show that this is order n squared.
433
00:26:07.000 --> 00:26:14.000
We want to show that n squared over two plus three and over two is smaller than or equal to something times n squared.
434
00:26:14.000 --> 00:26:20.000
Which of that something be?
435
00:26:20.000 --> 00:26:25.000
Okay. Let's figure it out.
436
00:26:25.000 --> 00:26:28.000
Here's a surefire way to do this.
437
00:26:28.000 --> 00:26:35.000
I know that n squared is bigger than n squared over two, right?
438
00:26:35.000 --> 00:26:39.000
Is n squared bigger than three and over two?
439
00:26:39.000 --> 00:26:42.000
Eventually.
440
00:26:42.000 --> 00:26:46.000
Is there an easy?
441
00:26:46.000 --> 00:26:50.000
If I thought of this as n squared, that means this is like three n squared.
442
00:26:50.000 --> 00:26:53.000
So three n squared is bigger than three and over two, right?
443
00:26:53.000 --> 00:26:55.000
Everyone believes that.
444
00:26:55.000 --> 00:27:00.000
So why did I do this? Why did I use three n squared to handle this?
445
00:27:00.000 --> 00:27:03.000
N squared to handle this?
446
00:27:03.000 --> 00:27:06.000
It gives me four n squared.
447
00:27:06.000 --> 00:27:13.000
This is definitely bigger than these two because one of the n squared is handles this one and one of the n squared is handled and three of the n squared is handled this one.
448
00:27:13.000 --> 00:27:15.000
Right? Make sense?
449
00:27:15.000 --> 00:27:16.000
All right.
450
00:27:16.000 --> 00:27:19.000
So this therefore is order n squared.
451
00:27:19.000 --> 00:27:26.000
If you do a similar thing for the omega case, it's even easier in the omega case here.
452
00:27:26.000 --> 00:27:28.000
There's no reason to look for another one.
453
00:27:28.000 --> 00:27:30.000
Now there's no reason at all.
454
00:27:30.000 --> 00:27:33.000
Right. Right. Don't go out of your way to look for a smaller one.
455
00:27:33.000 --> 00:27:40.000
This is bigger than what times n squared.
456
00:27:40.000 --> 00:27:41.000
Agreed?
457
00:27:41.000 --> 00:27:44.000
In this case, the omega was the easier part.
458
00:27:44.000 --> 00:27:47.000
Here the bigger was the easier part.
459
00:27:47.000 --> 00:27:51.000
The reason is these definitions are formalizing the idea that we don't care about the constants.
460
00:27:51.000 --> 00:27:55.000
We care about what happens after the numbers n get very, very large.
461
00:27:55.000 --> 00:27:58.000
We don't care about the two or the divide by two or the three.
462
00:27:58.000 --> 00:28:04.000
And this is a formal way of saying that we don't care about that.
463
00:28:04.000 --> 00:28:07.000
Okay. Let's do a...
464
00:28:07.000 --> 00:28:12.000
So do we need to state what the four n greater than whatever?
465
00:28:12.000 --> 00:28:17.000
In this case, it's true for all n. So the greater than whatever is just going to be zero.
466
00:28:17.000 --> 00:28:19.000
This is true for every n in the whole world.
467
00:28:19.000 --> 00:28:25.000
And a lot of times you can do it where that past a certain point is just past zero.
468
00:28:25.000 --> 00:28:29.000
n is fraction, close enough to zero, it's not true.
469
00:28:29.000 --> 00:28:31.000
So you can say n bigger than one.
470
00:28:31.000 --> 00:28:34.000
Certainly true for n bigger than one.
471
00:28:34.000 --> 00:28:38.000
Okay. I'm going to do one more, but I think it's a straightforward example.
472
00:28:38.000 --> 00:28:45.000
Then I want to do a harder example to show you how much manipulation you might need in order to do these things.
473
00:28:45.000 --> 00:28:53.000
So let's do this question.
474
00:28:53.000 --> 00:29:00.000
This is what Sam was talking about a second ago.
475
00:29:00.000 --> 00:29:04.000
Here's a polynomial.
476
00:29:04.000 --> 00:29:09.000
Sam says that if you have a polynomial and you want to know what the order of it is, what the complexity of it is,
477
00:29:09.000 --> 00:29:14.000
just go to the part that has the biggest exponent, ignore the constant in front of it, and that's what it is.
478
00:29:14.000 --> 00:29:16.000
So this should be big theta and to the fourth.
479
00:29:16.000 --> 00:29:18.000
And that's true and you can prove this theorem.
480
00:29:18.000 --> 00:29:21.000
Alright. So let's just see why and how the proof goes.
481
00:29:21.000 --> 00:29:23.000
We won't prove it, but I'll give you the intuition.
482
00:29:23.000 --> 00:29:25.000
Same as we did before.
483
00:29:25.000 --> 00:29:30.000
This is going to be smaller than or equal to 2n to the fourth.
484
00:29:30.000 --> 00:29:35.000
Another 5n to the fourth.
485
00:29:35.000 --> 00:29:38.000
Another 1n to the fourth.
486
00:29:38.000 --> 00:29:40.000
Another n to the fourth.
487
00:29:40.000 --> 00:29:42.000
So how many does that make altogether?
488
00:29:42.000 --> 00:29:47.000
1, 2, 7.
489
00:29:47.000 --> 00:29:49.000
It's smaller or equal to 9n to the fourth.
490
00:29:49.000 --> 00:29:57.000
You can always go ahead and dominate these terms by this major term.
491
00:29:57.000 --> 00:30:00.000
Alright.
492
00:30:00.000 --> 00:30:04.000
I'm not going to work for greater than or equal to 1 at least.
493
00:30:04.000 --> 00:30:07.000
You write that up again.
494
00:30:07.000 --> 00:30:14.000
2n to the fourths here, 5n to the fourths here, 1n to the fourth here, and 1n to the fourth here.
495
00:30:14.000 --> 00:30:17.000
You don't really need to put one in for this. It's just overkill.
496
00:30:17.000 --> 00:30:21.000
Put 7n to the fourth for the constant as well.
497
00:30:21.000 --> 00:30:25.000
You could do that and then it would be true for everything.
498
00:30:25.000 --> 00:30:27.000
You can make it 16.
499
00:30:27.000 --> 00:30:30.000
Not quite 17.
500
00:30:30.000 --> 00:30:33.000
We might as well make it 17.
501
00:30:33.000 --> 00:30:35.000
Alright, let me ask you a question.
502
00:30:35.000 --> 00:30:49.000
Is 2 to the n big theta 2 to the n plus 1?
503
00:30:49.000 --> 00:30:50.000
Here are the two parts.
504
00:30:50.000 --> 00:30:54.000
That means 2 to the n is bigger than or equal to some constant times 2 to the n plus 1
505
00:30:54.000 --> 00:31:00.000
and 2 to the n is smaller or equal to some other constant times 2 to the n plus 1.
506
00:31:00.000 --> 00:31:03.000
Well, that is just to be the constant.
507
00:31:03.000 --> 00:31:07.000
2 to the n plus 1 would be the same as 2 to the n.
508
00:31:07.000 --> 00:31:09.000
The time is constant 2.
509
00:31:09.000 --> 00:31:12.000
Okay.
510
00:31:12.000 --> 00:31:18.000
Well, you can't make an argument on the intuition from the theorem.
511
00:31:18.000 --> 00:31:20.000
So go back to the actual theorem.
512
00:31:20.000 --> 00:31:22.000
What should the Cb to make this true?
513
00:31:22.000 --> 00:31:25.000
One half.
514
00:31:25.000 --> 00:31:29.000
These are strictly equal when C equals a half.
515
00:31:29.000 --> 00:31:31.000
Right?
516
00:31:31.000 --> 00:31:35.000
Here, this is true when C equals 1.
517
00:31:35.000 --> 00:31:38.000
So here you use a half, here you use 1.
518
00:31:38.000 --> 00:31:42.000
So they are big theta of each other.
519
00:31:42.000 --> 00:31:45.000
Another question.
520
00:31:45.000 --> 00:31:52.000
That's what we're going to do with the n, too.
521
00:31:52.000 --> 00:31:54.000
Yes, sure, absolutely.
522
00:31:54.000 --> 00:31:55.000
Right.
523
00:31:55.000 --> 00:31:57.000
How about this?
524
00:31:57.000 --> 00:32:00.000
It's 2 to the 2n.
525
00:32:00.000 --> 00:32:02.000
Let's just do big O.
526
00:32:02.000 --> 00:32:09.000
It's 2 to the 2n, big O, 2 to the n.
527
00:32:09.000 --> 00:32:14.000
It's 2 to the 2n smaller than some constant times 2 to the n.
528
00:32:14.000 --> 00:32:17.000
How do you figure this out?
529
00:32:17.000 --> 00:32:20.000
I will try to do the n.
530
00:32:20.000 --> 00:32:23.000
Okay, let's try that idea.
531
00:32:23.000 --> 00:32:26.000
If you divide this by 2 to the n, what do you get?
532
00:32:26.000 --> 00:32:28.000
2 to the 2n divided by 2 to the n.
533
00:32:28.000 --> 00:32:30.000
You subtract the exponents, you get 2 to the n.
534
00:32:30.000 --> 00:32:35.000
So it's 2 to the n less than or equal to a constant for any constant in the whole world.
535
00:32:35.000 --> 00:32:39.000
Well, after you get past a certain point, this will also be bigger than any constant.
536
00:32:39.000 --> 00:32:41.000
So you're dead here.
537
00:32:41.000 --> 00:32:43.000
This is not ordered 2 to the n.
538
00:32:43.000 --> 00:32:46.000
It's definitely not big O 2 to the n.
539
00:32:46.000 --> 00:32:47.000
Okay?
540
00:32:47.000 --> 00:32:52.000
Because no matter how big a constant you pick, this will eventually be larger than that constant.
541
00:32:52.000 --> 00:32:57.000
Right.
542
00:32:57.000 --> 00:33:02.000
A good, fast way of deciding how to compare two functions, because of this trick,
543
00:33:02.000 --> 00:33:04.000
do you see how we divided there?
544
00:33:04.000 --> 00:33:07.000
A good fast way is to take the functions and divide one by the other.
545
00:33:07.000 --> 00:33:19.000
So for example, let's compare these two things.
546
00:33:19.000 --> 00:33:21.000
2 to the n and n squared.
547
00:33:21.000 --> 00:33:23.000
Remember a problem set on this?
548
00:33:23.000 --> 00:33:26.000
Which one of these is bigger than the other?
549
00:33:26.000 --> 00:33:30.000
For what n?
550
00:33:30.000 --> 00:33:32.000
Remember you approve that?
551
00:33:32.000 --> 00:33:33.000
Well, there's a reason.
552
00:33:33.000 --> 00:33:37.000
If you could prove something like this, then what do you know about n squared?
553
00:33:37.000 --> 00:33:47.000
n squared is less than or equal to 2 to the n for all n bigger than 5.
554
00:33:47.000 --> 00:33:53.000
That means that n squared is order 2 to the n.
555
00:33:53.000 --> 00:33:58.000
Well, that's not so interesting, but actually it's strictly less than, right?
556
00:33:58.000 --> 00:34:04.000
Why do you put in n greater than 5 on the problem set?
557
00:34:04.000 --> 00:34:07.000
Yeah, greater than 4.
558
00:34:07.000 --> 00:34:10.000
Yeah.
559
00:34:10.000 --> 00:34:12.000
No reason.
560
00:34:12.000 --> 00:34:14.000
Typo.
561
00:34:14.000 --> 00:34:17.000
This is strictly less than, if you can get something strictly less than,
562
00:34:17.000 --> 00:34:21.000
then instead of saying big O, we sometimes say smaller.
563
00:34:21.000 --> 00:34:24.000
And that means it's not only bounded above, but it's bounded strictly above.
564
00:34:24.000 --> 00:34:29.000
That it's really smaller than, that it has no chance of ever being the same.
565
00:34:29.000 --> 00:34:34.000
It still requires the restriction on n and the number of strictness.
566
00:34:34.000 --> 00:34:38.000
It's the same exact definition, except without the equal sign on the lesson.
567
00:34:38.000 --> 00:34:40.000
Just strictly less than.
568
00:34:40.000 --> 00:34:45.000
So it means it's a real real upper bound that you'll never ever reach.
569
00:34:45.000 --> 00:34:47.000
That you're definitely less than.
570
00:34:47.000 --> 00:34:49.000
The opportunity at the end is so much bigger.
571
00:34:49.000 --> 00:34:51.000
Right.
572
00:34:51.000 --> 00:34:54.000
No surprise you're saying. Good. It shouldn't be.
573
00:34:54.000 --> 00:34:58.000
If you switch this around, if you try to show that 2 to the n is order n squared,
574
00:34:58.000 --> 00:35:01.000
you won't be able to do it.
575
00:35:01.000 --> 00:35:05.000
2 to the n less than or equal to some constant times n squared.
576
00:35:05.000 --> 00:35:10.000
One way to show that you never can do this is to divide both sides,
577
00:35:10.000 --> 00:35:12.000
just like we did before.
578
00:35:12.000 --> 00:35:17.000
And then we have to show that 2 to the n over n squared is smaller than or equal to a constant c.
579
00:35:17.000 --> 00:35:19.000
For all n past a certain point.
580
00:35:19.000 --> 00:35:25.000
One way to do this is to take the limit of this as n goes to infinity.
581
00:35:25.000 --> 00:35:27.000
Put in very large numbers.
582
00:35:27.000 --> 00:35:31.000
If this limit gets bigger than a constant, then you can never do it.
583
00:35:31.000 --> 00:35:33.000
Then you won't get a big O there.
584
00:35:33.000 --> 00:35:39.000
But if the limit equals a constant, then you can use that constant here.
585
00:35:39.000 --> 00:35:41.000
So this limit goes to infinity.
586
00:35:41.000 --> 00:35:46.000
And you can go back to calculus and use all the tricks you can possibly think of to figure out limits
587
00:35:46.000 --> 00:35:49.000
and comparing one function to another.
588
00:35:49.000 --> 00:35:53.000
Take the function, divide it by the other, figure out its limit as you go to infinity.
589
00:35:53.000 --> 00:35:57.000
That's a sure way of comparing one to the other whether one is big O of the other.
590
00:35:57.000 --> 00:36:02.000
And you can use all the powerful theorems that calculus gives you about limits.
591
00:36:02.000 --> 00:36:04.000
Okay, questions about that?
592
00:36:04.000 --> 00:36:07.000
Well, with that is a situation where you have it now.
593
00:36:07.000 --> 00:36:09.000
Or would you actually have to do some...
594
00:36:09.000 --> 00:36:11.000
You have to do this limit.
595
00:36:11.000 --> 00:36:17.000
And that's infinity over infinity. And you can deal with that by taking the derivative of both of them.
596
00:36:17.000 --> 00:36:21.000
Yeah, I'm up to you. Did you guys learn how to take limits of things that turn out to infinity over infinity?
597
00:36:21.000 --> 00:36:23.000
Maybe not. But I'll tell you a theorem that's...
598
00:36:23.000 --> 00:36:26.000
I'll tell you the only theorem that's particularly useful here.
599
00:36:26.000 --> 00:36:31.000
That if you get a limit where when you plug in the infinity, you get kind of infinity on top and infinity on the bottom,
600
00:36:31.000 --> 00:36:35.000
then there's a more or less. There's a theorem that says,
601
00:36:35.000 --> 00:36:40.000
take the derivative of the top and the derivative of the bottom and redo the limit.
602
00:36:40.000 --> 00:36:47.000
And if that ends up being straight infinity, then this one's straight infinity.
603
00:36:47.000 --> 00:36:51.000
If that ends up having a real limit, then this one has a real limit.
604
00:36:51.000 --> 00:36:54.000
The thing about taking derivatives is that it makes it simpler.
605
00:36:54.000 --> 00:36:58.000
The derivative of this is approximately 2 to the n. It's 0.7 times 2 to the n more or less.
606
00:36:58.000 --> 00:37:00.000
And the derivative of this is 2n.
607
00:37:00.000 --> 00:37:02.000
Then you can do the derivatives again.
608
00:37:02.000 --> 00:37:06.000
The derivative of this would be 0.7, 0.7, 2 to the n. That's the second derivative.
609
00:37:06.000 --> 00:37:10.000
The second derivative of this is 2. So that limit goes to infinity.
610
00:37:10.000 --> 00:37:12.000
Therefore, the original limit goes to infinity.
611
00:37:12.000 --> 00:37:13.000
That rule is called...
612
00:37:13.000 --> 00:37:14.000
Lopital.
613
00:37:14.000 --> 00:37:16.000
Lopital's rule.
614
00:37:16.000 --> 00:37:19.000
I'm not sure Lopital discovered it, but it's called his rule.
615
00:37:19.000 --> 00:37:23.000
One of the first things you do in an algorithms class is talk about sorting.
616
00:37:23.000 --> 00:37:27.000
And when you do sorting, you talk about actual algorithms for sorting.
617
00:37:27.000 --> 00:37:28.000
Like we just did.
618
00:37:28.000 --> 00:37:31.000
Where the triangle numbers come back in.
619
00:37:31.000 --> 00:37:33.000
But another thing you do about sorting is you wonder,
620
00:37:33.000 --> 00:37:37.000
hey, what's the minimum amount of time it's going to take me to sort things?
621
00:37:37.000 --> 00:37:40.000
I know I can sort things in n squared. I just showed you that.
622
00:37:40.000 --> 00:37:42.000
But what's the minimum amount of time?
623
00:37:42.000 --> 00:37:44.000
What am I trying to beat?
624
00:37:44.000 --> 00:37:48.000
Well, you're trying to beat n squared, but how much better can you do?
625
00:37:48.000 --> 00:37:50.000
Can you get down to n?
626
00:37:50.000 --> 00:37:54.000
Well, you can prove that if you're using comparisons to sort,
627
00:37:54.000 --> 00:37:57.000
you won't do the proof here, but you can prove it in algorithms.
628
00:37:57.000 --> 00:38:02.000
That it takes at least big theta n log n to sort it.
629
00:38:02.000 --> 00:38:05.000
And you can, to sort numbers, counting the comparisons.
630
00:38:05.000 --> 00:38:06.000
You can't get down.
631
00:38:06.000 --> 00:38:07.000
But that's possible.
632
00:38:07.000 --> 00:38:08.000
You can't do better.
633
00:38:08.000 --> 00:38:09.000
Right.
634
00:38:09.000 --> 00:38:14.000
It's very rare that you can prove an optimum thing like this for an algorithm.
635
00:38:14.000 --> 00:38:18.000
You can always get an upper bound on the time for an algorithm by exhibiting an algorithm.
636
00:38:18.000 --> 00:38:21.000
But to say an algorithm needs to take this amount of time,
637
00:38:21.000 --> 00:38:22.000
you really need a clever argument.
638
00:38:22.000 --> 00:38:24.000
And this is a very clever argument.
639
00:38:24.000 --> 00:38:26.000
It uses binary trees.
640
00:38:26.000 --> 00:38:31.000
And it proves that the minimum number of steps the sort requires n log n.
641
00:38:31.000 --> 00:38:34.000
That's assuming you don't know anything about the numbers.
642
00:38:34.000 --> 00:38:35.000
That there's no restrictions.
643
00:38:35.000 --> 00:38:37.000
If you restrict the numbers, you can actually do a little better.
644
00:38:37.000 --> 00:38:41.000
But if you don't restrict anything about the numbers, n log n is the best you can do.
645
00:38:41.000 --> 00:38:43.000
Now, where does this come from?
646
00:38:43.000 --> 00:38:45.000
What really comes out of this proof is this.
647
00:38:45.000 --> 00:38:50.000
That you need this many steps, the log of n factorial.
648
00:38:50.000 --> 00:38:53.000
That's what really comes out of the proof.
649
00:38:53.000 --> 00:38:57.000
And then there's a whole big stage where we take the log of n factorial
650
00:38:57.000 --> 00:39:02.000
and you convince the class that that's really the same as big theta n log n.
651
00:39:02.000 --> 00:39:07.000
This comes up much more often in algorithms that you'll see it in other places.
652
00:39:07.000 --> 00:39:12.000
Because log rhythms come from trees and n factorials come from permutation.
653
00:39:12.000 --> 00:39:15.000
So it's basically a binary tree of permutations.
654
00:39:15.000 --> 00:39:17.000
And that's where that comes from.
655
00:39:17.000 --> 00:39:20.000
But I want to convince you, and here's the main thing I'm doing now,
656
00:39:20.000 --> 00:39:22.000
why this is the same as this.
657
00:39:22.000 --> 00:39:26.000
Why log of n factorial is the same as order n log n.
658
00:39:26.000 --> 00:39:29.000
And we're going to work with the definition and we're going to work with some algebra.
659
00:39:29.000 --> 00:39:33.000
And you'll see how mildly hairy some of these proofs can get.
660
00:39:33.000 --> 00:39:36.000
Okay, other questions so far?
661
00:39:36.000 --> 00:39:38.000
Yeah, Tony.
662
00:39:38.000 --> 00:39:43.000
Well, you said that that best case you can only get n log n for sorting.
663
00:39:43.000 --> 00:39:44.000
Right.
664
00:39:44.000 --> 00:39:45.000
And for theta, that's true.
665
00:39:45.000 --> 00:39:50.000
But depending on what numbers you have, the actual execution of a particular instance
666
00:39:50.000 --> 00:39:52.000
could happen in less time.
667
00:39:52.000 --> 00:39:53.000
Yes.
668
00:39:53.000 --> 00:39:57.000
Yes, we're talking about the overall algorithm time, which means the worst case.
669
00:39:57.000 --> 00:39:58.000
Yeah, right.
670
00:39:58.000 --> 00:40:02.000
I mean, a particular instance where say the numbers happen to be sorted
671
00:40:02.000 --> 00:40:04.000
and your algorithm just looks at them quickly and checks.
672
00:40:04.000 --> 00:40:10.000
And that would be done in linear time, in order n time.
673
00:40:10.000 --> 00:40:13.000
But that doesn't solve the problem, that just gets lucky.
674
00:40:13.000 --> 00:40:16.000
Right. Right. Right. Right.
675
00:40:16.000 --> 00:40:17.000
But you're 100% right.
676
00:40:17.000 --> 00:40:19.000
All right, so let's get back to this.
677
00:40:19.000 --> 00:40:22.000
How do we show that this is going to be big theta n log n?
678
00:40:22.000 --> 00:40:23.000
Yeah, you know.
679
00:40:23.000 --> 00:40:25.000
Why don't you just leave it as log in factorial, or why we do that?
680
00:40:25.000 --> 00:40:29.000
Oh, because, okay, I'll leave it as log in factorial.
681
00:40:29.000 --> 00:40:37.000
And I want to know where this compares to n squared, n, and 2 to the n, and n log n.
682
00:40:37.000 --> 00:40:39.000
These are kind of the stars in our universe.
683
00:40:39.000 --> 00:40:40.000
These are the things that come up a lot.
684
00:40:40.000 --> 00:40:44.000
And you come up with this, and if you don't know how it compares to these things,
685
00:40:44.000 --> 00:40:46.000
then it's just like a shooting star out of nowhere.
686
00:40:46.000 --> 00:40:50.000
So the reason we want to go back to here is because we know where it fits in.
687
00:40:50.000 --> 00:40:54.000
We know that it fits in between n and n squared, in a nice place called n log n.
688
00:40:54.000 --> 00:40:56.000
That's a good question.
689
00:40:56.000 --> 00:40:59.000
It's just a log n factorial to some people might not give them a sense.
690
00:40:59.000 --> 00:41:02.000
Maybe you think this is exponential or something, or who knows?
691
00:41:02.000 --> 00:41:04.000
Okay. That's a good question.
692
00:41:04.000 --> 00:41:06.000
Other questions?
693
00:41:06.000 --> 00:41:08.000
All right, let's go ahead and do this.
694
00:41:08.000 --> 00:41:12.000
Let's try to analyze log of n factorial.
695
00:41:12.000 --> 00:41:18.000
We want to show number one that it's less than or equal to some constant n log n.
696
00:41:18.000 --> 00:41:22.000
And then we're going to have to show that it's bigger than some other constant n log n.
697
00:41:22.000 --> 00:41:27.000
This will be the big ol' part, this will be the big omega part.
698
00:41:27.000 --> 00:41:31.000
All right, so this is going to be a lot of algebra and some math.
699
00:41:31.000 --> 00:41:38.000
And stick with me here because there's one clever idea.
700
00:41:38.000 --> 00:41:42.000
Let's do the first part because it's easier.
701
00:41:42.000 --> 00:41:45.000
What constant could we use here?
702
00:41:45.000 --> 00:41:49.000
And how could we get any handle on this at all?
703
00:41:49.000 --> 00:41:51.000
Sam says it's one.
704
00:41:51.000 --> 00:41:54.000
We believe Sam, right?
705
00:41:54.000 --> 00:42:00.000
You can raise log n to the log n to the n.
706
00:42:00.000 --> 00:42:03.000
You can do that.
707
00:42:03.000 --> 00:42:06.000
I see what you're thinking. That's a good idea.
708
00:42:06.000 --> 00:42:08.000
That's a good idea.
709
00:42:08.000 --> 00:42:13.000
It was obvious they'd less than n to the n because each of the terms is a pen or less.
710
00:42:13.000 --> 00:42:16.000
Let's go with your idea.
711
00:42:16.000 --> 00:42:22.000
Sam and Michael say that log n factorial is less than or equal to log n to the n.
712
00:42:22.000 --> 00:42:24.000
Everyone agree to that?
713
00:42:24.000 --> 00:42:27.000
Because this is just n times n minus 1 times n minus 2.
714
00:42:27.000 --> 00:42:30.000
And this is n times n times n times n times n times n.
715
00:42:30.000 --> 00:42:31.000
So here are all the terms.
716
00:42:31.000 --> 00:42:33.000
Each one is bigger than each of the terms here.
717
00:42:33.000 --> 00:42:39.000
So I agree that this is definitely bigger than this because n to the n is bigger than n factorial.
718
00:42:39.000 --> 00:42:46.000
And if you remember your log rules, this equals exactly n log n.
719
00:42:46.000 --> 00:42:50.000
So log n factorial is less than or equal to n log n.
720
00:42:50.000 --> 00:42:52.000
So I could use the constant one.
721
00:42:52.000 --> 00:42:54.000
And Sam's right and Michael's got a good way to look at it.
722
00:42:54.000 --> 00:42:57.000
So let's go with your way.
723
00:42:57.000 --> 00:43:04.000
I wanted to do it a little bit of a different way because it leads to the next problem, which is much harder.
724
00:43:04.000 --> 00:43:08.000
The way I wanted to try to show you how to do it is let's use the other rules for logs.
725
00:43:08.000 --> 00:43:10.000
And yet I got to remember back month 0 now.
726
00:43:10.000 --> 00:43:11.000
How do you do logs?
727
00:43:11.000 --> 00:43:13.000
Let's expand this a little bit.
728
00:43:13.000 --> 00:43:15.000
What's the log of n factorial?
729
00:43:15.000 --> 00:43:22.000
Log n plus log n minus 1.
730
00:43:22.000 --> 00:43:24.000
These are all multiplied.
731
00:43:24.000 --> 00:43:29.000
So if you run the log through it, you add all the log values together.
732
00:43:29.000 --> 00:43:33.000
Plus log of 2 plus log of 1.
733
00:43:33.000 --> 00:43:35.000
All right, there it is.
734
00:43:35.000 --> 00:43:39.000
That's log n factorial.
735
00:43:39.000 --> 00:43:47.000
We want to show that this is bigger than or equal to some constant times n log n.
736
00:43:47.000 --> 00:43:49.000
We got to pick a constant to make that work.
737
00:43:49.000 --> 00:43:55.000
Lock it off in a little.
738
00:43:55.000 --> 00:43:58.000
Joe, sorry, would you?
739
00:43:58.000 --> 00:44:07.000
If you combine all those terms, it becomes n log n.
740
00:44:07.000 --> 00:44:08.000
I don't think so.
741
00:44:08.000 --> 00:44:12.000
If you combine all these terms, it becomes log n factorial, right?
742
00:44:12.000 --> 00:44:14.000
Well, combine all the terms.
743
00:44:14.000 --> 00:44:15.000
Yeah, though.
744
00:44:15.000 --> 00:44:17.000
Except for the log n.
745
00:44:17.000 --> 00:44:18.000
Except for this?
746
00:44:18.000 --> 00:44:19.000
Yeah.
747
00:44:19.000 --> 00:44:23.000
And we can divide both sides by log n.
748
00:44:23.000 --> 00:44:27.000
We're going to have 1 plus n to the left side log n factorial.
749
00:44:27.000 --> 00:44:31.000
We'll get log of n minus 1 factorial divided by n or something like that.
750
00:44:31.000 --> 00:44:32.000
Maybe.
751
00:44:32.000 --> 00:44:37.000
The most log of n minus 1 factorial would be equal to.
752
00:44:37.000 --> 00:44:39.000
You're dividing by log n.
753
00:44:39.000 --> 00:44:41.000
You're dividing by log n?
754
00:44:41.000 --> 00:44:42.000
That's a lot of trouble.
755
00:44:42.000 --> 00:44:47.000
It's a lot of trouble because you get log n minus 1 divided by log n minus 2 divided by.
756
00:44:47.000 --> 00:44:48.000
So those guys back together.
757
00:44:48.000 --> 00:44:50.000
So you get log n minus 1 factorial.
758
00:44:50.000 --> 00:44:51.000
Right.
759
00:44:51.000 --> 00:44:52.000
And then you divide.
760
00:44:52.000 --> 00:44:54.000
So you get 1 plus log n minus 1 factorial.
761
00:44:54.000 --> 00:45:00.000
Is greater than or equal to c1 times n times 1.
762
00:45:00.000 --> 00:45:01.000
Right.
763
00:45:01.000 --> 00:45:03.000
But you get log n minus 1 factorial over log n.
764
00:45:03.000 --> 00:45:05.000
That's kind of ugly.
765
00:45:05.000 --> 00:45:10.000
If you divide log n factorial by log n, you just get the factorial.
766
00:45:10.000 --> 00:45:12.000
They all cancel out.
767
00:45:12.000 --> 00:45:15.000
Except for the information point.
768
00:45:15.000 --> 00:45:17.000
Well, let's get back to this question.
769
00:45:17.000 --> 00:45:19.000
What is what should this cb?
770
00:45:19.000 --> 00:45:20.000
Is 1 going to work?
771
00:45:20.000 --> 00:45:21.000
No.
772
00:45:21.000 --> 00:45:22.000
No way.
773
00:45:22.000 --> 00:45:24.000
1 works for less than or equal.
774
00:45:24.000 --> 00:45:26.000
So it's unlikely 1 is going to work for greater than or equal.
775
00:45:26.000 --> 00:45:29.000
You want a number bigger than 1 or smaller than 1 here.
776
00:45:29.000 --> 00:45:33.000
Smaller than 1 because you need it to be bigger than ms value.
777
00:45:33.000 --> 00:45:35.000
How much smaller than 1 do you need?
778
00:45:35.000 --> 00:45:36.000
Look, you can just guess.
779
00:45:36.000 --> 00:45:37.000
You can't pick 0.
780
00:45:37.000 --> 00:45:42.000
That's not allowed.
781
00:45:42.000 --> 00:45:45.000
You got to pick something which is bigger than 0.
782
00:45:45.000 --> 00:45:47.000
So you could pick, I don't know, you could pick a tenth.
783
00:45:47.000 --> 00:45:48.000
You could pick a hundredth.
784
00:45:48.000 --> 00:45:51.000
But it's just a stab in the dark.
785
00:45:51.000 --> 00:45:53.000
Let's get something that we think is going to work.
786
00:45:53.000 --> 00:45:58.000
It will work, but 1 17 is so much nicer.
787
00:45:58.000 --> 00:46:00.000
Yes, 1 17 is nice.
788
00:46:00.000 --> 00:46:01.000
Let's see if we can get a half to work.
789
00:46:01.000 --> 00:46:04.000
But why would we expect a half to work?
790
00:46:04.000 --> 00:46:06.000
Why would you ever think anything is going to work here?
791
00:46:06.000 --> 00:46:07.000
Maybe it's not true.
792
00:46:07.000 --> 00:46:08.000
I mean, why do you think this is true?
793
00:46:08.000 --> 00:46:10.000
Why is it going to work?
794
00:46:10.000 --> 00:46:12.000
You want to cut this in half soon?
795
00:46:12.000 --> 00:46:14.000
Half at an over two.
796
00:46:14.000 --> 00:46:19.000
All right, the reason what I'm hoping you look at here is an idea that you've seen before
797
00:46:19.000 --> 00:46:21.000
and you've seen it in the triangle numbers.
798
00:46:21.000 --> 00:46:24.000
What was one way to add up the triangle numbers?
799
00:46:24.000 --> 00:46:28.000
First and the last, second and the second to last?
800
00:46:28.000 --> 00:46:32.000
You got no guarantee that's going to work here, but at least it's something to try.
801
00:46:32.000 --> 00:46:36.000
One of the things you're trying to get in discrete math is a big bag of tricks.
802
00:46:36.000 --> 00:46:40.000
If you came in with hardly any tricks and you want to leave with a lot of tricks
803
00:46:40.000 --> 00:46:42.000
and you want to be able to do two things.
804
00:46:42.000 --> 00:46:46.000
When you pull out a trick, you want to be able to recognize it and know what to do with it.
805
00:46:46.000 --> 00:46:49.000
So it's not like, oh, this is a pneumatic double hammer.
806
00:46:49.000 --> 00:46:51.000
I don't know how to use this, but I better put that back.
807
00:46:51.000 --> 00:46:56.000
You want to be able to use all the tools in your basket, but you know what makes you really good?
808
00:46:56.000 --> 00:47:02.000
What makes you really good is you see this big complicated machine and you say, oh, I know the tool that's going to open that machine
809
00:47:02.000 --> 00:47:04.000
and you go right in and you grab it.
810
00:47:04.000 --> 00:47:05.000
That's the hard part.
811
00:47:05.000 --> 00:47:12.000
But minimally, what you should expect to get is I know every tool in my chest and I know which ones more or less are helpful.
812
00:47:12.000 --> 00:47:15.000
So here, let's try this tool, whether it works or not.
813
00:47:15.000 --> 00:47:17.000
Before we guess the constant.
814
00:47:17.000 --> 00:47:22.000
So here's what we do. We have log 1 plus log n.
815
00:47:22.000 --> 00:47:25.000
Log n minus 1.
816
00:47:25.000 --> 00:47:31.000
Is this a good way to pair them? Plus log 2.
817
00:47:31.000 --> 00:47:33.000
Is that all right? Well, we can try.
818
00:47:33.000 --> 00:47:36.000
What's the middle term going to look like more or less?
819
00:47:36.000 --> 00:47:43.000
We're less like this.
820
00:47:43.000 --> 00:47:48.000
We just chopped the thing in half. This is what Sam suggested because he has good intuition about these things.
821
00:47:48.000 --> 00:47:52.000
He's done a million of these things and he's got a great bag of tricks.
822
00:47:52.000 --> 00:47:57.000
So he had a census would work and it maybe he was going to work, but let's look at it.
823
00:47:57.000 --> 00:47:59.000
We've got these things all paired up.
824
00:47:59.000 --> 00:48:06.000
We've got half as many pairs here as we had terms up here and each one comes in two.
825
00:48:06.000 --> 00:48:09.000
Log 1 log n. Log n minus 1 log 2.
826
00:48:09.000 --> 00:48:16.000
And the middle terms are log n over 2 log n over 2.
827
00:48:16.000 --> 00:48:20.000
Because as you get to the, you're going 1, 2, 3 all the way up to n.
828
00:48:20.000 --> 00:48:23.000
So the middle term is going to be halfway and over 2.
829
00:48:23.000 --> 00:48:24.000
The question.
830
00:48:24.000 --> 00:48:25.000
There's only one term.
831
00:48:25.000 --> 00:48:28.000
Right. What if there's an odd number of terms and these two will differ by 1.
832
00:48:28.000 --> 00:48:32.000
So you know what? I should say fudging here a little.
833
00:48:32.000 --> 00:48:34.000
You're right, Sam. I mean, I should really be very careful about this.
834
00:48:34.000 --> 00:48:37.000
If it's an odd number of terms, this misses a little.
835
00:48:37.000 --> 00:48:40.000
But it actually won't affect our argument. So it won't hurt.
836
00:48:40.000 --> 00:48:44.000
There would never be two. I just said.
837
00:48:44.000 --> 00:48:48.000
There's one over n.
838
00:48:48.000 --> 00:48:49.000
That's the right way to write it.
839
00:48:49.000 --> 00:48:52.000
No, that's the important thing of the.
840
00:48:52.000 --> 00:48:54.000
You're round up, you're round down.
841
00:48:54.000 --> 00:49:00.000
That's actually right. But you try to do an analysis with this and the analysis becomes harder and kind of obscures your main idea.
842
00:49:00.000 --> 00:49:04.000
But if you want to be very precise, round up here and round down here.
843
00:49:04.000 --> 00:49:06.000
That I think works fine.
844
00:49:06.000 --> 00:49:10.000
But don't get. Let that go. Don't get involved with the details.
845
00:49:10.000 --> 00:49:13.000
Work the details out later if you get the main idea first.
846
00:49:13.000 --> 00:49:16.000
How do we? We're still not even up to the constant part.
847
00:49:16.000 --> 00:49:20.000
We're not even close. What's going on here?
848
00:49:20.000 --> 00:49:26.000
One plus log n is log n. Log 2 plus log n minus log n.
849
00:49:26.000 --> 00:49:31.000
This is log n times log 1. So that's log n. This is log 2 times n minus 1.
850
00:49:31.000 --> 00:49:39.000
This is log 3 n minus 3. And the last one is log minus 2.
851
00:49:39.000 --> 00:49:46.000
Thank you. And the last one is log dot dot dot n over 2.
852
00:49:46.000 --> 00:49:49.000
More or less than over 2.
853
00:49:49.000 --> 00:49:52.000
Okay. So now we've got it written like that.
854
00:49:52.000 --> 00:49:55.000
How many terms are here altogether?
855
00:49:55.000 --> 00:49:58.000
And over 2 terms. Right? Half as many terms as we have before.
856
00:49:58.000 --> 00:50:04.000
That's a clue that we should try to put a one half here.
857
00:50:04.000 --> 00:50:07.000
Right? That's a clue. But where do we go next?
858
00:50:07.000 --> 00:50:10.000
We got log n here. Right?
859
00:50:10.000 --> 00:50:12.000
We got log as something here.
860
00:50:12.000 --> 00:50:16.000
Don't know if it's bigger than log n or smaller than log n.
861
00:50:16.000 --> 00:50:20.000
10 minus k times k has us its maximum k over 2.
862
00:50:20.000 --> 00:50:23.000
So it's going to go up to n.
863
00:50:23.000 --> 00:50:25.000
Okay. We can do something a little. That's true.
864
00:50:25.000 --> 00:50:30.000
But we can do something a little bit. We can avoid even if you didn't know that.
865
00:50:30.000 --> 00:50:32.000
What if you didn't have that in your bag of tricks?
866
00:50:32.000 --> 00:50:40.000
This is bigger than one half n.
867
00:50:40.000 --> 00:50:50.000
Log n over 2.
868
00:50:50.000 --> 00:50:55.000
And let me try to explain why.
869
00:50:55.000 --> 00:50:57.000
Let's do this piece by piece.
870
00:50:57.000 --> 00:51:01.000
How do you know this part is bigger than log n over 2?
871
00:51:01.000 --> 00:51:04.000
Because it's n over 2 times something. Right?
872
00:51:04.000 --> 00:51:07.000
How do you know this one's bigger than log n over 2?
873
00:51:07.000 --> 00:51:12.000
Because one of these two, either 2 or n minus 1,
874
00:51:12.000 --> 00:51:15.000
is bigger than log n over 2. Right?
875
00:51:15.000 --> 00:51:17.000
You have 2 times n minus 1.
876
00:51:17.000 --> 00:51:21.000
One of them is going to be bigger than half of n.
877
00:51:21.000 --> 00:51:24.000
3 of n minus 2. One of them is going to be bigger than half of n.
878
00:51:24.000 --> 00:51:28.000
So every one of these terms, this one, this one, this one.
879
00:51:28.000 --> 00:51:33.000
Every single one of them is bigger than log n over 2.
880
00:51:33.000 --> 00:51:35.000
So everyone agree with that?
881
00:51:35.000 --> 00:51:37.000
I have too many confused faces.
882
00:51:37.000 --> 00:51:40.000
Let me say it again. Because this is an easy idea if you just think about it for a second.
883
00:51:40.000 --> 00:51:43.000
What's going on here? I got these numbers going from 1 to n.
884
00:51:43.000 --> 00:51:45.000
And these numbers going down from n minus 1.
885
00:51:45.000 --> 00:51:50.000
So 2 times n minus 1. One of those numbers is bigger than half of n. Right?
886
00:51:50.000 --> 00:51:56.000
So this is log 2 plus log n minus 1. Right?
887
00:51:56.000 --> 00:51:59.000
This one alone is bigger than log n over 2.
888
00:51:59.000 --> 00:52:03.000
This one alone is bigger than log n over 2.
889
00:52:03.000 --> 00:52:08.000
That one alone is bigger than log n over 2.
890
00:52:08.000 --> 00:52:15.000
Who doesn't get it?
891
00:52:15.000 --> 00:52:23.000
No, maybe this wasn't the best way.
892
00:52:23.000 --> 00:52:24.000
Yeah, question.
893
00:52:24.000 --> 00:52:28.000
Why are you multiplying?
894
00:52:28.000 --> 00:52:29.000
Why we did this step?
895
00:52:29.000 --> 00:52:34.000
How you're getting to log 2 times n minus 1 from?
896
00:52:34.000 --> 00:52:37.000
Is that just something you can do with log 2?
897
00:52:37.000 --> 00:52:41.000
If you add 2 logs together, then it's the log of their product.
898
00:52:41.000 --> 00:52:45.000
But following on that line, we did this because someone suggested it.
899
00:52:45.000 --> 00:52:49.000
But now, maybe we didn't need to do it. Look back here.
900
00:52:49.000 --> 00:52:56.000
Each of these pieces is something that adds up
901
00:52:56.000 --> 00:52:58.000
almost to n. Right?
902
00:52:58.000 --> 00:53:02.000
So one of these two, either the 2 or the n minus 1 is bigger than half of it.
903
00:53:02.000 --> 00:53:05.000
Here it's n and 1. This one's bigger than half.
904
00:53:05.000 --> 00:53:10.000
Here it's n minus 2 and 3.
905
00:53:10.000 --> 00:53:12.000
One of them is going to be bigger than half of n.
906
00:53:12.000 --> 00:53:17.000
So each pair of these, each pair is bigger than log of n over 2.
907
00:53:17.000 --> 00:53:20.000
And how many pairs are there?
908
00:53:20.000 --> 00:53:22.000
There's n over 2 pairs.
909
00:53:22.000 --> 00:53:24.000
Yes, Sam, what do you want to say?
910
00:53:24.000 --> 00:53:29.000
Can you give me a minute on the board to show it much more clearly?
911
00:53:29.000 --> 00:53:30.000
All right.
912
00:53:30.000 --> 00:53:34.000
As soon as I'm done, you can have five minutes and show it more clearly.
913
00:53:34.000 --> 00:53:37.000
All right, so here's where we're up to.
914
00:53:37.000 --> 00:53:39.000
We have this original log n factorial.
915
00:53:39.000 --> 00:53:40.000
It reduces down to here.
916
00:53:40.000 --> 00:53:44.000
And now I know it's bigger than a half n log n over 2.
917
00:53:44.000 --> 00:53:46.000
Are we done?
918
00:53:46.000 --> 00:53:47.000
Almost.
919
00:53:47.000 --> 00:53:51.000
We have to write log n over 2 as log n.
920
00:53:51.000 --> 00:54:03.000
Log n over 2 is log n minus the log of 2.
921
00:54:03.000 --> 00:54:10.000
So if I multiply this out, I get n over 2 log n minus n over 2 log 2.
922
00:54:10.000 --> 00:54:13.000
And over 2 log 2 is just the constant.
923
00:54:13.000 --> 00:54:15.000
It's 1. Log base 2 of 2 is 1.
924
00:54:15.000 --> 00:54:18.000
So these two are the same.
925
00:54:18.000 --> 00:54:21.000
So I've gotten the number of half.
926
00:54:21.000 --> 00:54:25.000
I've shown that my sum is bigger than n over 2 log n.
927
00:54:25.000 --> 00:54:30.000
But it's bigger than n over 2 log n minus n over 2.
928
00:54:30.000 --> 00:54:32.000
And I don't want that minus n over 2 in there.
929
00:54:32.000 --> 00:54:34.000
I've got to get that out of there.
930
00:54:34.000 --> 00:54:37.000
So there's one extra little step, a little fudge step I have to do here.
931
00:54:37.000 --> 00:54:49.000
And here's what I do.
932
00:54:49.000 --> 00:54:55.000
I note that this part here with the negative is actually bigger or equal to n over 4 log n.
933
00:54:55.000 --> 00:55:00.000
As long as n is past a certain number, as long as n is bigger than 4.
934
00:55:00.000 --> 00:55:04.000
You could check this part yourself by doing the algebra.
935
00:55:04.000 --> 00:55:07.000
So what constant actually works in the end?
936
00:55:07.000 --> 00:55:13.000
The constant that works is a fourth, as long as n is bigger than 4.
937
00:55:13.000 --> 00:55:17.000
And you might be able to go away with a half, as long as n is past something.
938
00:55:17.000 --> 00:55:21.000
But I didn't bother trying to calculate what that past spot should be.
939
00:55:21.000 --> 00:55:25.000
So instead, I just changed it to here where the algebra is easier to do.
940
00:55:25.000 --> 00:55:27.000
And I rushed through that at the end.
941
00:55:27.000 --> 00:55:33.000
But the upshot of this is that log n factorial is big theta n log n.
942
00:55:33.000 --> 00:55:36.000
The upper bound big O part is easy to do.
943
00:55:36.000 --> 00:55:38.000
The gamma part is much harder to do.
944
00:55:38.000 --> 00:55:41.000
It requires a lot of algebraic manipulation.
945
00:55:41.000 --> 00:55:44.000
Sam's going to show you an easier way in a second.
946
00:55:44.000 --> 00:55:50.000
It ends up being bigger than n over 2 log n minus n over 2, which is bigger than or equal to n over 4 log n.
947
00:55:50.000 --> 00:55:58.000
So the C is a fourth, and the n zero is four, or the x zero is four.
948
00:55:58.000 --> 00:56:03.000
Donut question.
949
00:56:03.000 --> 00:56:05.000
I meant omega.
950
00:56:05.000 --> 00:56:07.000
There's no gamma.
951
00:56:07.000 --> 00:56:09.000
Alpha delta.
952
00:56:09.000 --> 00:56:12.000
I was thinking of a fret.
953
00:56:12.000 --> 00:56:13.000
Teresia.
954
00:56:13.000 --> 00:56:17.000
I did this quickly too.
955
00:56:17.000 --> 00:56:22.000
Log of n divided by 2 is the log of n minus the log of 2.
956
00:56:22.000 --> 00:56:25.000
Okay?
957
00:56:25.000 --> 00:56:28.000
So it's a half n log n. That's this.
958
00:56:28.000 --> 00:56:31.000
Minus a half n log 2.
959
00:56:31.000 --> 00:56:33.000
Log 2 is just one.
960
00:56:33.000 --> 00:56:35.000
Log base 2 of 2 is 1.
961
00:56:35.000 --> 00:56:37.000
So that's minus a half n.
962
00:56:37.000 --> 00:56:38.000
That's a good question.
963
00:56:38.000 --> 00:56:41.000
Teresia, I really went through that way too fast.
964
00:56:41.000 --> 00:56:42.000
But that's true.
965
00:56:42.000 --> 00:56:44.000
And that's just that stupid minus a half.
966
00:56:44.000 --> 00:56:47.000
So we make the constant a little smaller to handle that.
967
00:56:47.000 --> 00:56:50.000
So all of our logs are about base 2.
968
00:56:50.000 --> 00:56:53.000
In this particular case,
969
00:56:53.000 --> 00:56:58.000
it actually is a binary tree, and it really is log base 2.
970
00:56:58.000 --> 00:57:00.000
But in order to do that, you have to have.
971
00:57:00.000 --> 00:57:03.000
If we didn't have it to know it was log base 2,
972
00:57:03.000 --> 00:57:06.000
then at this point it would be n over 2 times some constant.
973
00:57:06.000 --> 00:57:10.000
Right? All logs are a constant factor multiplied by other logs.
974
00:57:10.000 --> 00:57:13.000
So if it wasn't, if it was base 10, then I just have it
975
00:57:13.000 --> 00:57:16.000
a little number there, n over 2 times some other number.
976
00:57:16.000 --> 00:57:21.000
And it wouldn't affect the details too much.
977
00:57:21.000 --> 00:57:24.000
Other other questions?
978
00:57:24.000 --> 00:57:27.000
All right, so Sam, I'll give you five minutes right now.
979
00:57:27.000 --> 00:57:29.000
Yeah, Baruch, quick, yeah.
980
00:57:29.000 --> 00:57:31.000
I see what you did.
981
00:57:31.000 --> 00:57:32.000
I think I followed that.
982
00:57:32.000 --> 00:57:33.000
Ah.
983
00:57:33.000 --> 00:57:37.000
Twitter, it doesn't just doesn't play well with what they see on the board.
984
00:57:37.000 --> 00:57:42.000
I mean, you have log n plus log n minus 1 plus log 1.
985
00:57:42.000 --> 00:57:43.000
All this? Yeah.
986
00:57:43.000 --> 00:57:48.000
On the other side, on the other side, you have log n plus log n plus log n.
987
00:57:48.000 --> 00:57:50.000
No, divided by 2.
988
00:57:50.000 --> 00:57:54.000
No, no, but what you're trying to show is that this is
989
00:57:54.000 --> 00:57:58.000
a larger greater than the n log n, right?
990
00:57:58.000 --> 00:58:00.000
Greater than some constant times n log n.
991
00:58:00.000 --> 00:58:03.000
So I'm going to use a half for that constant.
992
00:58:03.000 --> 00:58:06.000
It's not bigger than n log n itself.
993
00:58:06.000 --> 00:58:07.000
That's true.
994
00:58:07.000 --> 00:58:09.000
It's bigger than half of it, though.
995
00:58:09.000 --> 00:58:13.000
It's bigger than some constant fraction of it.
996
00:58:13.000 --> 00:58:16.000
The constant that I ended up using here is a half.
997
00:58:16.000 --> 00:58:21.000
So you're okay, the one that constant would do it for every n,
998
00:58:21.000 --> 00:58:24.000
largest, the certain n doesn't do it.
999
00:58:24.000 --> 00:58:25.000
It's true.
1000
00:58:25.000 --> 00:58:26.000
Oh, you wouldn't believe that.
1001
00:58:26.000 --> 00:58:27.000
You don't believe that.
1002
00:58:27.000 --> 00:58:28.000
Oh, okay.
1003
00:58:28.000 --> 00:58:29.000
But it's, I don't believe it.
1004
00:58:29.000 --> 00:58:31.000
I don't know what to trick me.
1005
00:58:31.000 --> 00:58:35.000
Okay, so before San does five minutes, I'll just say,
1006
00:58:35.000 --> 00:58:38.000
I'll give you my little story about believe it.
1007
00:58:38.000 --> 00:58:41.000
I was in, I don't know, 10th grade or something.
1008
00:58:41.000 --> 00:58:45.000
And there was a kid in my class named Bodner, Amos Bodner.
1009
00:58:45.000 --> 00:58:48.000
And Math was a little challenging for Amos.
1010
00:58:48.000 --> 00:58:51.000
And he studied his head off for this New York, I don't know,
1011
00:58:51.000 --> 00:58:54.000
some standard exam that you had to take.
1012
00:58:54.000 --> 00:58:57.000
And you had to pass this to get on to the next class.
1013
00:58:57.000 --> 00:59:01.000
And he was one of these nervous kind of people that was always worrying about it.
1014
00:59:01.000 --> 00:59:03.000
He would study hours and hours.
1015
00:59:03.000 --> 00:59:05.000
It was just horrible to watch him suffer this way.
1016
00:59:05.000 --> 00:59:07.000
And he was ready and ready.
1017
00:59:07.000 --> 00:59:09.000
And he wasn't the most likable kid either.
1018
00:59:09.000 --> 00:59:11.000
She didn't really feel so sorry for him.
1019
00:59:11.000 --> 00:59:13.000
And he would work and work and work and work.
1020
00:59:13.000 --> 00:59:15.000
He wasn't a happy kid.
1021
00:59:15.000 --> 00:59:21.000
So anyway, he took this, I wonder where he is today.
1022
00:59:21.000 --> 00:59:23.000
Oh no!
1023
00:59:23.000 --> 00:59:30.000
It just says how oblivious I am.
1024
00:59:30.000 --> 00:59:32.000
The name's up and changed.
1025
00:59:32.000 --> 00:59:35.000
Should have changed his name.
1026
00:59:35.000 --> 00:59:36.000
Anyway.
1027
00:59:36.000 --> 00:59:38.000
You can't leave it.
1028
00:59:38.000 --> 00:59:39.000
Oh gee.
1029
00:59:39.000 --> 00:59:43.000
I'm sorry.
1030
00:59:43.000 --> 00:59:47.000
So he took this test and the teachers, you know,
1031
00:59:47.000 --> 00:59:49.000
calling out the grades and the teachers said,
1032
00:59:49.000 --> 00:59:51.000
well, everyone has a choice.
1033
00:59:51.000 --> 00:59:53.000
I will say you're great out loud.
1034
00:59:53.000 --> 00:59:55.000
You can come up and look at it here.
1035
00:59:55.000 --> 00:59:57.000
So everybody comes to them and they make a decision.
1036
00:59:57.000 --> 00:59:58.000
Out loud or not.
1037
00:59:58.000 --> 00:59:59.000
Whatever.
1038
00:59:59.000 --> 01:00:02.000
So I finally get to him and he sits there squirming in his seat.
1039
01:00:02.000 --> 01:00:04.000
Oh, I don't know if you should say that loud.
1040
01:00:04.000 --> 01:00:05.000
Oh, maybe he should.
1041
01:00:05.000 --> 01:00:06.000
And he goes back.
1042
01:00:06.000 --> 01:00:08.000
Everybody in the class goes, oh, I'm just saying.
1043
01:00:08.000 --> 01:00:11.000
Finally, he says, tell it to me out loud.
1044
01:00:11.000 --> 01:00:14.000
And the teacher with a completely straight face.
1045
01:00:14.000 --> 01:00:15.000
You need to do 65 to pass.
1046
01:00:15.000 --> 01:00:17.000
The teacher reads his grades and says,
1047
01:00:17.000 --> 01:00:19.000
Bodner, 64.
1048
01:00:19.000 --> 01:00:21.000
And stares at him like this.
1049
01:00:21.000 --> 01:00:23.000
Everybody thought he was joking, you know,
1050
01:00:23.000 --> 01:00:24.000
because he's a funny guy that teacher
1051
01:00:24.000 --> 01:00:26.000
and he could conceivably have done this.
1052
01:00:26.000 --> 01:00:28.000
So Bodner goes, you're kidding.
1053
01:00:28.000 --> 01:00:29.000
I don't believe it.
1054
01:00:29.000 --> 01:00:30.000
I don't believe it.
1055
01:00:30.000 --> 01:00:32.000
And he's freaking out saying, I don't believe it.
1056
01:00:32.000 --> 01:00:33.000
I don't believe it.
1057
01:00:33.000 --> 01:00:35.000
And the teacher's not cracking the smile yet.
1058
01:00:35.000 --> 01:00:36.000
It's over thinking, oh my god.
1059
01:00:36.000 --> 01:00:37.000
It's like completely like not a joke.
1060
01:00:37.000 --> 01:00:40.000
And while the teacher goes, he goes, is it really true?
1061
01:00:40.000 --> 01:00:43.000
And teacher is 64, Bodner.
1062
01:00:43.000 --> 01:00:45.000
So at this point, he's like virtually in tears
1063
01:00:45.000 --> 01:00:46.000
and he's freaking out.
1064
01:00:46.000 --> 01:00:47.000
And he says, I don't believe it.
1065
01:00:47.000 --> 01:00:48.000
And he doesn't shut up and he keeps,
1066
01:00:48.000 --> 01:00:49.000
I hope we're an over again.
1067
01:00:49.000 --> 01:00:50.000
I don't believe it.
1068
01:00:50.000 --> 01:00:51.000
I don't believe it.
1069
01:00:51.000 --> 01:00:52.000
I don't believe it.
1070
01:00:52.000 --> 01:00:55.000
So finally, the teacher never cracking another face
1071
01:00:55.000 --> 01:00:57.000
except his little prist lips telling him 64 looks at him
1072
01:00:57.000 --> 01:00:59.000
and says, well, believe it, Bodner.
1073
01:00:59.000 --> 01:01:01.000
And that was the end of the story.
1074
01:01:01.000 --> 01:01:03.000
So anytime anybody asks me and says, like, I don't believe it.
1075
01:01:03.000 --> 01:01:05.000
It's like, I always think of that story.
1076
01:01:05.000 --> 01:01:07.000
And now the whole world knows it.
1077
01:01:07.000 --> 01:01:10.000
And he really got a 64 well.
1078
01:01:10.000 --> 01:01:11.000
Believe it, Bodner.
1079
01:01:11.000 --> 01:01:12.000
Poor guy.
1080
01:01:12.000 --> 01:01:15.000
Anyway, here's your five minutes.
1081
01:01:15.000 --> 01:01:16.000
I'm done.
1082
01:01:16.000 --> 01:01:17.000
I'm done, Brad.
1083
01:01:17.000 --> 01:01:18.000
Yeah.
1084
01:01:18.000 --> 01:01:21.000
I don't know which way Sam's going to do.
1085
01:01:21.000 --> 01:01:24.000
But if Sam has a better way here, you should see it.
1086
01:01:24.000 --> 01:01:26.000
Because he often has a better way.
1087
01:01:26.000 --> 01:01:28.000
In fact, Toriel is then, as I was then,
1088
01:01:28.000 --> 01:01:33.000
like this one, then, then by this two, down to one.
1089
01:01:33.000 --> 01:01:38.000
To get an upper limit on that, we substituted
1090
01:01:38.000 --> 01:01:41.000
for each of these terms and itself.
1091
01:01:41.000 --> 01:01:45.000
So in fact, Toriel is going to be less than or equal to n
1092
01:01:45.000 --> 01:01:46.000
to the n.
1093
01:01:46.000 --> 01:01:49.000
We really don't have to put the equal in.
1094
01:01:49.000 --> 01:01:53.000
But now we want to get a lower limit on that.
1095
01:01:53.000 --> 01:01:56.000
If we simply substituted one for each of these,
1096
01:01:56.000 --> 01:01:59.000
it's not going to be a very useful lower limit.
1097
01:01:59.000 --> 01:02:01.000
But I'm suggesting that we cut it off
1098
01:02:01.000 --> 01:02:04.000
at, let's say, n over 2.
1099
01:02:04.000 --> 01:02:12.000
And then it keeps going.
1100
01:02:12.000 --> 01:02:17.000
Well, in fact, Toriel is going to be greater than one
1101
01:02:17.000 --> 01:02:21.000
half of the front tail because we've cut off the rear tail,
1102
01:02:21.000 --> 01:02:23.000
and not only added more.
1103
01:02:23.000 --> 01:02:25.000
It's going to be greater than n, then, then, then,
1104
01:02:25.000 --> 01:02:28.000
minus one all the way down to n over 2.
1105
01:02:28.000 --> 01:02:32.000
And now I'm going to substitute n over 2 for each of these terms.
1106
01:02:32.000 --> 01:02:35.000
Each of these terms is greater than n over 2 or equal to it.
1107
01:02:35.000 --> 01:02:39.000
So in fact, Toriel is greater than n over 2,
1108
01:02:39.000 --> 01:02:42.000
and there are n over 2 such terms.
1109
01:02:42.000 --> 01:02:46.000
I'm fudging a little because n over 2 may be
1110
01:02:46.000 --> 01:02:48.000
halfway in between two integers.
1111
01:02:48.000 --> 01:02:52.000
But the fudge, you can work out for yourself.
1112
01:02:52.000 --> 01:02:57.000
So log of n factorial is going to be greater than log of
1113
01:02:57.000 --> 01:03:04.000
n over 2 to the n over 2, which is n over 2 times log of n over 2,
1114
01:03:04.000 --> 01:03:15.000
which is 1 half n log n minus log 2.
1115
01:03:15.000 --> 01:03:21.000
And log of n minus log 2, we dealt with before.
1116
01:03:21.000 --> 01:03:25.000
But any time you have a sum of two terms or a difference
1117
01:03:25.000 --> 01:03:28.000
of two terms in which one term over powers the other,
1118
01:03:28.000 --> 01:03:30.000
you can effectively ignore the second term.
1119
01:03:30.000 --> 01:03:34.000
So this gave you the one half n log n.
1120
01:03:34.000 --> 01:03:40.000
Again, instead of substituting at the n,
1121
01:03:40.000 --> 01:03:42.000
where you have to substitute one for all of these terms.
1122
01:03:42.000 --> 01:03:46.000
And that's not going to give you a useful inequality.
1123
01:03:46.000 --> 01:03:49.000
You cut it off halfway and you substitute the left side
1124
01:03:49.000 --> 01:03:52.000
by its lowest number, which is n over 2.
1125
01:03:52.000 --> 01:03:55.000
And you're going to get as a lower bound, n over 2 raised to the
1126
01:03:55.000 --> 01:03:56.000
n over 2 power.
1127
01:03:56.000 --> 01:04:01.000
Exactly the same as the upper bound was n to the nth power.
1128
01:04:01.000 --> 01:04:03.000
I think that's easy to say.
1129
01:04:03.000 --> 01:04:06.000
Sam is basically showing it to you before you take the log
1130
01:04:06.000 --> 01:04:07.000
from both sides.
1131
01:04:07.000 --> 01:04:09.000
And then takes the log from both sides at the n.
1132
01:04:09.000 --> 01:04:13.000
And it is easier to see that way, I think.
1133
01:04:13.000 --> 01:04:15.000
Sam also mentions this.
1134
01:04:15.000 --> 01:04:17.000
He says, look, if you have n over 2 log n, and then there's
1135
01:04:17.000 --> 01:04:21.000
a minus something, since n log n is bigger than n,
1136
01:04:21.000 --> 01:04:24.000
you can just forget about this minus n over 2,
1137
01:04:24.000 --> 01:04:28.000
because as n gets big, sooner or later, this will overpower that.
1138
01:04:28.000 --> 01:04:30.000
And that is true.
1139
01:04:30.000 --> 01:04:32.000
But if you really want to use the theorem specifically,
1140
01:04:32.000 --> 01:04:34.000
you have to say at what point that's going to overpower,
1141
01:04:34.000 --> 01:04:37.000
that'll be that x0, or else you just can do this little trick
1142
01:04:37.000 --> 01:04:40.000
that I did, which is fixing the c.
1143
01:04:40.000 --> 01:04:42.000
That's the first term of 17.
1144
01:04:42.000 --> 01:04:44.000
Always is overpowered by 17.
1145
01:04:44.000 --> 01:04:46.000
That's 17 would work here, right?
1146
01:04:46.000 --> 01:04:47.000
Okay.
1147
01:04:47.000 --> 01:04:52.000
So that's it.