Adversarial Argument and Searching Lower Bound (Searching: Algorithms and Lower Bounds)
4Today we learn what a lower bound is for a computational problem. We see what the concept of an adversary is in this context, then together we prove that we require linear time to solve the search problem more broadly.
Time Stamps:
0:00 Opening and recap
1:24 What are upper bounds and lower bounds for solving a problem
5:00 How might you prove a lower bound holds?
6:59 Introduction to adversarial arguments
18:02 Idea for the search problem's lower bound
21:19 The proof
26:34 What does this mean?
27:13 Closing
Have a beautiful day!
Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
Draikou
Patreon Supporters (Basic Support):
Patreon Supporters (Supporter Access!):
Eric R
-----------------------------------------------------------
Become a supporter today! To support my work and mission to provide free or accessible Computer Science education (especially in theory), subscribe to the channel, share my videos. Please donate and contribute to support my work for more content:
PATREON: https://www.patreon.com/PageWizard
SUBSCRIBESTAR: https://www.subscribestar.com/drpage
PAYPAL: https://paypal.me/pagewizard
Follow also at:
FACEBOOK: https://www.facebook.com/DanielRPage
TWITTER: https://twitter.com/PageWizardGLE
QUORA: https://www.quora.com/profile/Daniel-R-Page
TWITCH: https://www.twitch.tv/pagewizard
#ComputerScience
#Algorithms
#Lowerbounds