Algorithms - Introduction

Complexity cases §

• Best case: algorithm running with best set of data, fastest performance
• Worst case: algorithm running with worst set of data, slowest performance
• Average case: in-between
• For algorithm analysis we want worst case

Big-O Notation §

• Denoted $O(f(n))$ where $n$ is size of upper bound
• Small bound that is not tight (precise): $o(f(n))$
• Lower bound: $\Omega(f(n))$$
• Mathematical definition:
  $$f(x)\text{ is }O(g(x))⟺x_0,c.\forall x>x_0.f(x)\le cg(x)$$

Asymptotic Behaviour §

Common Runtime Complexities §

• O(N): linear time
• O($N^2$): quadratic time
  • NP-complete problems
    • Best known algorithm involves exponential time
    • Solve one in polynomial time -> solve all problems in that class
• O($2^N$): exponential time
• O($n\log n$)