Data Structures & Algorithms Notes Page

Analysis TL;DR

• We mostly look at the worst case analysis
• We are interested in the growth of the runtime as the input size n grows to a large value n
• We will ignore the lower order terms and constants
• $T(n) = O(f(n))$ → $c * f(n)$ is an upper bound
• $T(n) = \Omega(f(n))$ → $c * f(n)$ is a lower bound
• $T(n) = \theta(f(n))$ → It is both the upper and lower bound

Mathematical Proof Techniques:

There are a few of them:

1. By deduction or direct proof
2. By contradiction
3. By Induction
4. By Counterexample

The Direct Proof:

What is it: