Relates the speedup of a sub-task to the resulting speedup of the whole. Trivially true, but often needed to knock down false intuition.
Used to abstract away units and fixed overhead when analyzing resource usage.
Traditional square one of theoretical computer science, with many practical applications.
Illustrates many recurring themes. Understanding the proof and usage of the pumping lemma will help you understand and apply more famous, advanced results (e.g. anything involving Turing Machines).