SCT Lecture 03: Complexity Theory

On October 21, 2011, I gave a co-lecture on the Basics of Complexity Theory.

Complexity Theory describes the expected performance of some algorithm in terms of the order of the variables inputted. For many contests, we are concerned with the asymptotic performance of some algorithm for the largest test cases (specifically with the worst-case scenario). This is useful for predicting whether a given program will run in the allotted time. The lecture can be found on the Senior Computer Team website, or viewed here: