Order Notation

?

?# Keyboard Navigation

## Global Keys

[, < / ], > Jump to previous / next episode

W, K, P / S, J, N Jump to previous / next marker

t / T Toggle theatre / SUPERtheatre mode

V Revert filter to original state Y Select link (requires manual Ctrl-c)## Menu toggling

q Quotes
r References
f Filter
y Link
c Credits
## In-Menu Movement

## Quotes and References Menus

Enter Jump to timecode

## Quotes, References and Credits Menus

o Open URL (in new tab)
## Filter Menu

x, Space Toggle category and focus next

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus## Filter and Link Menus

z Toggle filter / linking mode
## Credits Menu

Enter Open URL (in new tab)

W, K, P / S, J, N Jump to previous / next marker

t / T Toggle theatre / SUPERtheatre mode

V Revert filter to original state Y Select link (requires manual Ctrl-c)

a

w

s

s

d

h
j
k
l

←

↑

↓

↓

→

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus

⏫

Previous: 'Refining Renderer Sort Keys'

⏫

1:03Set the stage for the day

1:03Set the stage for the day

1:03Set the stage for the day

2:57Blackboard: Order Notation

2:57Blackboard: Order Notation

2:57Blackboard: Order Notation

4:13Blackboard: "unit"

4:13Blackboard: "unit"

4:13Blackboard: "unit"

5:50Blackboard: Linear "scale", e.g. stamping envelopes

5:50Blackboard: Linear "scale", e.g. stamping envelopes

5:50Blackboard: Linear "scale", e.g. stamping envelopes

8:39Blackboard: Nonlinear "scale", e.g. checking if any envelopes are addressed to the same person

8:39Blackboard: Nonlinear "scale", e.g. checking if any envelopes are addressed to the same person

8:39Blackboard: Nonlinear "scale", e.g. checking if any envelopes are addressed to the same person

14:02Blackboard: Why we care about linearity

14:02Blackboard: Why we care about linearity

14:02Blackboard: Why we care about linearity

15:57Blackboard: How this determines scalability

15:57Blackboard: How this determines scalability

15:57Blackboard: How this determines scalability

18:00Blackboard: Why we don't care about the constant when considering an algorithm's scalability

18:00Blackboard: Why we don't care about the constant when considering an algorithm's scalability

18:00Blackboard: Why we don't care about the constant when considering an algorithm's scalability

21:22Blackboard: How this translates into code

21:22Blackboard: How this translates into code

21:22Blackboard: How this translates into code

23:37Blackboard: Big O notation indicates "worst-case running time"

23:37Blackboard: Big O notation indicates "worst-case running time"

23:37Blackboard: Big O notation indicates "worst-case running time"

26:49Blackboard: "randomized algorithms"

26:49Blackboard: "randomized algorithms"

26:49Blackboard: "randomized algorithms"

28:34Blackboard: P (polynomial) vs NP (nondeterministic polynomial)

28:34Blackboard: P (polynomial) vs NP (nondeterministic polynomial)

28:34Blackboard: P (polynomial) vs NP (nondeterministic polynomial)

35:50Blackboard: On classifying problems as P or NP, e.g. "Boolean satisfiability problem"

35:50Blackboard: On classifying problems as P or NP, e.g. "Boolean satisfiability problem"

35:50Blackboard: On classifying problems as P or NP, e.g. "Boolean satisfiability problem"

40:45Blackboard: "NP-completeness"^{α}

40:45Blackboard: "NP-completeness"^{α}

40:45Blackboard: "NP-completeness"^{α}

45:12Blackboard: *Gotcha! e.g. "Travelling Salesman Problem"

45:12Blackboard: *Gotcha! e.g. "Travelling Salesman Problem"

45:12Blackboard: *Gotcha! e.g. "Travelling Salesman Problem"

52:14Blackboard: Sorting

52:14Blackboard: Sorting

52:14Blackboard: Sorting

53:39handmade_render_group.cpp: Note that the current SortEntries function is O(n^2)

53:39handmade_render_group.cpp: Note that the current SortEntries function is O(n^2)

53:39handmade_render_group.cpp: Note that the current SortEntries function is O(n^2)

54:02Blackboard: Why SortEntries is O(n^2)

54:02Blackboard: Why SortEntries is O(n^2)

54:02Blackboard: Why SortEntries is O(n^2)

55:17Blackboard: On how to make sorting not be O(n^2)

55:17Blackboard: On how to make sorting not be O(n^2)

55:17Blackboard: On how to make sorting not be O(n^2)

56:35Blackboard: Walk through our current (Bubble sort) algorithm

56:35Blackboard: Walk through our current (Bubble sort) algorithm

56:35Blackboard: Walk through our current (Bubble sort) algorithm

58:13Blackboard: Walk through a "divide and conquer" (Merge sort) algorithm

58:13Blackboard: Walk through a "divide and conquer" (Merge sort) algorithm

58:13Blackboard: Walk through a "divide and conquer" (Merge sort) algorithm

1:04:30Blackboard: Compare these two algorithms

1:04:30Blackboard: Compare these two algorithms

1:04:30Blackboard: Compare these two algorithms

1:07:08Blackboard: Divide and conquer algorithms are O(n log n)

1:07:08Blackboard: Divide and conquer algorithms are O(n log n)

1:07:08Blackboard: Divide and conquer algorithms are O(n log n)

1:08:35Blackboard: Solidify the concept of the merge sort algorithm and "dynamic programming"

1:08:35Blackboard: Solidify the concept of the merge sort algorithm and "dynamic programming"

1:08:35Blackboard: Solidify the concept of the merge sort algorithm and "dynamic programming"

1:14:28Q&A

🗩

1:14:28Q&A

🗩

1:14:28Q&A

🗩

1:21:12 : Has anyone definitively proven that Travelling Salesman could not be in P, or is that still potentially NP-hard?

1:21:12 : Has anyone definitively proven that Travelling Salesman could not be in P, or is that still potentially NP-hard?

1:23:12: Have they proven that it doesn't have a P verifier?

1:23:12: Have they proven that it doesn't have a P verifier?

1:23:12: Have they proven that it doesn't have a P verifier?

1:27:05Blackboard: "in P" / "not in P" vs "NP-complete"

1:27:05Blackboard: "in P" / "not in P" vs "NP-complete"

1:27:05Blackboard: "in P" / "not in P" vs "NP-complete"

1:38:09Wrap up with a recap

🗩

1:38:09Wrap up with a recap

🗩

1:38:09Wrap up with a recap

🗩

⏬

Next: 'Examples of Sorting Algorithms'

⏬