Return to Video

04-02 Analyzing Alice's Algorithm

  • 0:00 - 0:09
    And the correct answer here is O(2n*n²) and the reason why this is correct is as follows--
  • 0:09 - 0:16
    so the first line here takes constant amount of times so that's not going to be relevant.
  • 0:16 - 0:26
    Now, this loop here lines 2 to 5 are executed 2n*, so the question is each time this interloop here
  • 0:26 - 0:29
    lines 3 to 5 is executed, how much time does that take.
  • 0:29 - 0:36
    So checking of the assignment is valid, takes O(2n²*), then if the assignment is valid,
  • 0:36 - 0:42
    we need an additional O(n)+O(1), so an additional O(n) time because this here is constant,
  • 0:42 - 0:44
    so we can ignore it.
  • 0:44 - 0:52
    So the maximum time that lines 3 to 5 take is O(n²)+O(n)+O(1),
  • 0:52 - 1:01
    so the largest growing term here is O(n²)--so the interloop takes O(n²*) and that is executed 2n*.
  • 1:01 - 1:08
    So that's why the running time of Alice's algorithm is O(2n*n²),
  • 1:08 - 1:12
    and the good thing is that because we have our own notation, we could do this analysis
  • 1:12 - 1:16
    without actually concretely stating how all of these algorithm is programmed.
  • 1:16 -
    So as I hoped you see, it's quite a useful notation to have.
Title:
04-02 Analyzing Alice's Algorithm
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
01:21
Amara Bot added a translation

English subtitles

Revisions