Return to Video

## 03-01 Big O Notation

• 0:00 - 0:04
Big O notation is the final tool for analyzing algorithms
• 0:04 - 0:08
that you need to know about before we can analyze Alice algorithm.
• 0:08 - 0:11
As we've just seen even talking about worst-case running time
• 0:11 - 0:14
can be a bit tricky if we're trying to be very precise.
• 0:14 - 0:19
We have to identify the worst-case input in detail, which can be counter intuitive
• 0:19 - 0:21
and then work through a lot of different cases.
• 0:21 - 0:27
And also as we noticed it's annoying to have to count every single step an algorithm makes.
• 0:27 - 0:32
So for example if you have two algorithms and one had a running time of 2n²+23 time steps
• 0:32 - 0:38
and the other one had 2n²+27 time steps, you wouldn't really care about the 23 or the 27.
• 0:38 - 0:41
You would say that essentially they have the same running time.
• 0:41 - 0:45
So we are going to introduce a huge simplification
• 0:45 - 0:49
to stating running times and that is called Big O-notation.
• 0:49 - 0:52
If you've had an algorithm course before, you should already be familiar with this
• 0:52 - 0:55
but we'll review it here just to make sure you understand.
• 0:55 - 0:59
So let's say we have two algorithms, algorithm A and algorithm B,
• 0:59 - 1:05
and algorithm A has a running time 3n²-n+10 for an input of size n,
• 1:05 - 1:12
and algorithm B has a running time of 2^n-50n+256.
• 1:12 - 1:18
So what I would like you think about is which of these two algorithms you would prefer
• 1:18 - 1:23
if you don't know anything about the input other than that you're going to get different sizes.
• 1:23 - 1:28
So no other structural assumptions or anything else that you know.
• 1:28 - 1:32
And I would like you to check this box if you think it's algorithm A that if you take
• 1:32 -
in general and this box if you think it's algorithm B.
Title:
03-01 Big O Notation
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
01:36
 Amara Bot added a translation

• Amara Bot