Order Notation — Handmade Hero — Episode Guide

1:03Set the stage for the day

2:57Blackboard: Order Notation

4:13Blackboard: "unit"

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

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

14:02Blackboard: Why we care about linearity

15:57Blackboard: How this determines scalability

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

21:22Blackboard: How this translates into code

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

26:49Blackboard: "randomized algorithms"

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

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

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

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

52:14Blackboard: Sorting

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

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

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

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

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

1:04:30Blackboard: Compare these two algorithms

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: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:12cmuratori Has anyone definitively proven that Travelling Salesman could not be in P, or is that still potentially NP-hard?

🗪

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

🗪

1:21:12cmuratori 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:12cmuratori Have they proven that it doesn't have a P verifier?

🗪

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

🗪

1:23:12cmuratori 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: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

🗩

Keyboard Navigation

Global Keys

Menu toggling

In-Menu and Index Controls

Quotes and References Menus and Index

Quotes, References and Credits Menus

Filter Menu

Filter and Link Menus

Credits Menu