“Computer Science is no more about computers than astronomy is about telescopes.” Edsger W. Dijkstra

##

Proving an upper bound means you have proven that the algorithm will use no more than some limit on a resource.

Proving a lower bound means you have proven that the algorithm will use no less than some limit on a resource.

MIT Design And Analysis Of Algorithms Overview, Interval Scheduling Divide & Conquer: Convex Hull, Median Finding Divide & Conquer: FFT Divide & Conquer: van Emde Boas Trees Amortization: Amortized Analysis Randomization: Matrix Multiply, Quicksort Randomization: Skip Lists Randomization: Universal & Perfect Hashing Augmentation: Range Trees Dynamic Programming: Advanced DP Dynamic Programming: All-Pairs Shortest Paths Greedy Algorithms: Minimum Spanning Tree Incremental Improvement: Max Flow, Min Cut Incremental Improvement: Matching Linear Programming: LP, reductions, Simplex Complexity: P, NP, NP-completeness, Reductions Complexity: Approximation Algorithms Complexity: Fixed-Parameter Algorithms Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees Cryptography: Hash Functions Cryptography: Encryption Cache-Oblivious Algorithms: Medians & Matrices Cache-Oblivious Algorithms: Searching & Sorting