Notes/Advanced Algorithms/Complexity.md

date	type
02.09.2024	theoretical

\mathcal{O}

Complexity

• Time Complexity: amount of time an algorithm takes to complete as a function of the size of its input.
• Space Complexity: amount of memory it uses as a function of the size of its input.

Big O

• Formal Definition:

  Big O notation, \mathcal{O}(f(n)), describes the upper bound of the time or space complexity of an algorithm in terms of the input size n. It characterizes the worst-case scenario of an algorithm's growth rate.

  Formally, a function T(n) is said to be \mathcal{O}(f(n)) if there exist positive constants c and n_0 such that for all n \geq n_0:

  
  0 \leq T(n) \leq c \cdot f(n).
  

  This means that T(n) will grow at most as fast as f(n), up to a constant multiple c, for sufficiently large n.

Informally:

Big-O notation provides an upper limit on:

• Time: How long an algorithm will take.
• Space: How much memory it will require. It helps compare algorithms by focusing on their growth rate and ignoring constant factors.

Other Notations for Growth Rates

1. Big-O (\mathcal{O}(f(n))):

   • Describes the upper bound (worst-case) of T(n).
   • Informally: T(n) grows no faster than f(n).
   • Formal Definition:

     
     T(n) \text{ is } \mathcal{O}(f(n)) \iff \exists c > 0, n_0 > 0 \text{ such that } T(n) \leq c \cdot f(n) \text{ for all } n \geq n_0.
     

2. Big-Omega (\Omega(f(n))):

   • Describes the lower bound (best-case) of T(n).
   • Informally: T(n) grows at least as fast as f(n).
   • Formal Definition:

     
     T(n) \text{ is } \Omega(f(n)) \iff \exists c > 0, n_0 > 0 \text{ such that } T(n) \geq c \cdot f(n) \text{ for all } n \geq n_0.
     

3. Big-Theta (\Theta(f(n))):

   • Describes the exact bound (tight bound) of T(n).
   • Informally: T(n) grows exactly as fast as f(n).
   • Formal Definition:

     
     T(n) \text{ is } \Theta(f(n)) \iff T(n) \text{ is } \mathcal{O}(f(n)) \text{ and } T(n) \text{ is } \Omega(f(n)).
     

4. Little-O (o(f(n))):

   • Describes a loose upper bound of T(n).
   • Informally: T(n) grows strictly slower than f(n).
   • Formal Definition:

     
     T(n) \text{ is } o(f(n)) \iff \forall c > 0, \exists n_0 > 0 \text{ such that } T(n) < c \cdot f(n) \text{ for all } n \geq n_0.
     

Think of growth rates as vehicles on a highway:

• \mathcal{O}(f(n)): T(n) cannot go faster than f(n).
• \Omega(f(n)): T(n) cannot go slower than f(n).
• \Theta(f(n)): T(n) moves at the exact same speed as f(n).
• o(f(n)): T(n) moves slower than f(n) and never catches up.