In this lecture we discuss the complement of the discovery of algorithms, proving lower bounds for problems. Next time I'll consider another lower bound result for sorting.

Time Stamps:
0:00 Opening
2:25 Upper Bounds (on solving a problem, best-known algorithms wrt time complexity), with discussion wrt searching and sorting
23:45 Lower Bounds
26:45 Idea of an Adversary (Adversarial Argument)
37:53 Lower Bounds on Searching an Unsorted Array
45:47 Lower Bounds on Computing the Maximum in an unsorted array.

свернуть