5. Big-Oh Family (2)

17/02/23

$Θ$ is an equivalence relation

• Any relation that is Reflexive, Symmetric and Transitive
• is an equivalence relation
• Behaves like a equality

Little-Oh - Definition

Definition - Given (positive) functions $f(n)$ and $g(n)$ we say that $f(n) == o(g(n))$ if for all positive (real) constants $c>0$ there exists $n_0$ such that $f(n) < cg(n)$ for all $n\ge n_0$

Usage rules

• Cam also do multiplication:
• $f1$ is $o(g1)$, $f2$ is $o(g2)$ implies $f1*f2$ is $o(g1*g2)$

Mnemonics

• Big-Oh - Less than or equal $\le$
• Big-Omega - Greater than or equal $\ge$
• Big-Theta - Equal $=$
• little-oh - Strictly less than $<$

Asymptotic Algorithm Analysis

• The asymptotic analysis of an algorithm determines the running time in big-Oh notation
• To perform the asymptotic analysis
  • We find the worst-case number of primitive operations executed as a function of the input size
  • We express this function with big-Oh notation
• Since constant factors and lower-order terms are eventually dropped anyhow, we can disregard them when counting primitive operations

Caveats & Cautions

• Point of big-Oh-family is that it can hide constants and lower-order terms; but sometimes these are important
• Worst case might happen too rarely to matter

Rules for little-Oh

Multiplication

big-Oh * little-Oh