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

English subtitles

Revisions