1 complexity

Defined relative to the size of input: T(n)

1.1 space complexity

The peak asymptotic space (memory) needed in an algorithm.

1.2 time complexity

The asymptotic time (operations) needed in an algorithm.

Base unit of operations are the elementary operations.

1.2.1 dominating instruction

A set of instructions for which their asymptotic running time is equal to the asymptotic running time of the whole algorithm.

1.2.2 cases

• Worst-case: the worst time complexity for a specific input
• Average-case: the average time complexity from all inputs

1.3 master theorem

T(n) = aT(\lfloor \frac{n}{b} \rfloor) + f(n) where f(n) = \Theta(n^\alpha)

• \log_ba < \alpha \implies T(n) = \Theta(n^\alpha)
• \log_ba = \alpha \implies T(n) = \Theta(n^\alpha \log n)
• \log_ba > \alpha \implies T(n) = \Theta(n^{\log_ba})