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

a
w
s
d
h j k l


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)
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:14:56quartertron NP stands for Nondeterministic Polynomial. Plus some other minor problems. Otherwise, well done
🗪
1:14:56quartertron NP stands for Nondeterministic Polynomial. Plus some other minor problems. Otherwise, well done
🗪
1:14:56quartertron NP stands for Nondeterministic Polynomial. Plus some other minor problems. Otherwise, well done
🗪
1:16:39cubercaleb For the record the remark I made earlier about Rust was not serious. Also, isn't mergesort n*log(n)?
🗪
1:16:39cubercaleb For the record the remark I made earlier about Rust was not serious. Also, isn't mergesort n*log(n)?
🗪
1:16:39cubercaleb For the record the remark I made earlier about Rust was not serious. Also, isn't mergesort n*log(n)?
🗪
1:17:08Longboolean So unit testing a function that computes a path for the traveling salesman problem would require writing the algorithm twice, the second one testing the first?
🗪
1:17:08Longboolean So unit testing a function that computes a path for the traveling salesman problem would require writing the algorithm twice, the second one testing the first?
🗪
1:17:08Longboolean So unit testing a function that computes a path for the traveling salesman problem would require writing the algorithm twice, the second one testing the first?
🗪
1:18:04fiveshot97 Do you think a computer science major is a good path to go? I'm in it now
🗪
1:18:04fiveshot97 Do you think a computer science major is a good path to go? I'm in it now
🗪
1:18:04fiveshot97 Do you think a computer science major is a good path to go? I'm in it now
🗪
1:19:05insofaras You say "exponential"
🗪
1:19:05insofaras You say "exponential"
🗪
1:19:05insofaras You say "exponential"
🗪
1:19:08Busy_Beaver To say that a problem is not solvable in polynomial time, you just say "The problem is not in P"
🗪
1:19:08Busy_Beaver To say that a problem is not solvable in polynomial time, you just say "The problem is not in P"
🗪
1:19:08Busy_Beaver To say that a problem is not solvable in polynomial time, you just say "The problem is not in P"
🗪
1:21:12Casey Muratori: Has anyone definitively proven that Travelling Salesman could not be in P, or is that still potentially NP-hard?
1:21:12Casey Muratori: Has anyone definitively proven that Travelling Salesman could not be in P, or is that still potentially NP-hard?
1:21:12Casey Muratori: Has anyone definitively proven that Travelling Salesman could not be in P, or is that still potentially NP-hard?
1:22:44Busy_Beaver TSP is NP-complete, so it is also in NP, so it DOES have a polynomial verifier
🗪
1:22:44Busy_Beaver TSP is NP-complete, so it is also in NP, so it DOES have a polynomial verifier
🗪
1:22:44Busy_Beaver TSP is NP-complete, so it is also in NP, so it DOES have a polynomial 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:23:12: Have they proven that it doesn't have a P verifier?
1:25:33Busy_Beaver Well it depends which TSP problem we are actually talking about
🗪
1:25:33Busy_Beaver Well it depends which TSP problem we are actually talking about
🗪
1:25:33Busy_Beaver Well it depends which TSP problem we are actually talking about
🗪
1:26:44quiensab3 Wouldn't saying that something is "NINPY" imply that P != NP? (Did we win a $1M prize?)
🗪
1:26:44quiensab3 Wouldn't saying that something is "NINPY" imply that P != NP? (Did we win a $1M prize?)
🗪
1:26:44quiensab3 Wouldn't saying that something is "NINPY" imply that P != NP? (Did we win a $1M prize?)
🗪
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:30:42Longboolean Idea: The game should include a traveling salesman, who ponders these things...
🗪
1:30:42Longboolean Idea: The game should include a traveling salesman, who ponders these things...
🗪
1:30:42Longboolean Idea: The game should include a traveling salesman, who ponders these things...
🗪
1:30:54cubercaleb Will we go into more complex sort algorithms like radix sort? Also, is the space requirement of mergesort something that needs to be take into consideration for Handmade Hero?
🗪
1:30:54cubercaleb Will we go into more complex sort algorithms like radix sort? Also, is the space requirement of mergesort something that needs to be take into consideration for Handmade Hero?
🗪
1:30:54cubercaleb Will we go into more complex sort algorithms like radix sort? Also, is the space requirement of mergesort something that needs to be take into consideration for Handmade Hero?
🗪
1:31:45quartertron Since you didn't go to college, when did you first get interested in or at least start learning all about big O?
🗪
1:31:45quartertron Since you didn't go to college, when did you first get interested in or at least start learning all about big O?
🗪
1:31:45quartertron Since you didn't go to college, when did you first get interested in or at least start learning all about big O?
🗪
1:33:25insofaras I'm not sure we can prove something is not in P unless it is undecidable or we can prove P != NP
🗪
1:33:25insofaras I'm not sure we can prove something is not in P unless it is undecidable or we can prove P != NP
🗪
1:33:25insofaras I'm not sure we can prove something is not in P unless it is undecidable or we can prove P != NP
🗪
1:33:54Connor_Rentz By the way, 8^2 doesn't equal 16
🗪
1:33:54Connor_Rentz By the way, 8^2 doesn't equal 16
🗪
1:33:54Connor_Rentz By the way, 8^2 doesn't equal 16
🗪
1:37:31quartertron I shall dig through my copy of Computers and Intractability by Gary and Johnson tonight
🗪
1:37:31quartertron I shall dig through my copy of Computers and Intractability by Gary and Johnson tonight
🗪
1:37:31quartertron I shall dig through my copy of Computers and Intractability by Gary and Johnson tonight
🗪
1:37:41quartertron Hmm, first sentence contains the word whimsical so it's looking good so far
🗪
1:37:41quartertron Hmm, first sentence contains the word whimsical so it's looking good so far
🗪
1:37:41quartertron Hmm, first sentence contains the word whimsical so it's looking good so far
🗪
1:38:09Wrap up with a recap
🗩
1:38:09Wrap up with a recap
🗩
1:38:09Wrap up with a recap
🗩