Complexity Analysis

Relevant Classes: EECS 281, EECS 376

At it’s core, it attempts to answer the question: Given an algorithm and input size $n$, how many steps are needed?

The major metrics that are used are:

• Best Case
• Worst Case
• Average Case

Notation and Terminology:

• $n$: Input Size
• $f(n)$: Maximum number of steps taken by an algorithm when input has size $n$
• $O(f(n))$: Complexity class of $f(n)$. (Big-O Notation)