Complexity

• Time Complexity
• Space Complexity
  • We generally mean auxiliary space complexity which excludes space for the input

Asymptotic Notation

Syntax

• All functions defined are for $n\in {\mathbb{N}}_0$ or its subset and the functions are asymptotically non-negative, that is the functions are non-negative for sufficiently large $n$
• When we say $f(n)=O(g(n))$ we actually mean $f(n)\in O(g(n))$
• More precisely

$$O(g(n))=\{f(n):\exists c>0,n_0>0\text{such that}0\le f(n)\le c\cdot g(n),\forall n\ge n_0\}$$

Big Notations

• Big-O
  • Upper bound
  • $f(n)\in O(g(n))⟺\exists c>0,n_0>0:f(n)\le c\cdot g(n)\forall n\ge n_0$
• Big-Theta
  • Tight Bound
  • $f(n)\in \Theta (g(n))⟺\exists c_1,c_2>0,n_0>0:c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)\forall n\ge n_0$
• Big-Omega
  • Lower Bound
  • $f(n)\in \Omega (g(n))⟺\exists c>0,n_0>0:c\cdot g(n)\le f(n)\forall n\ge n_0$
• $O,\Omega ,\Theta$ themselves aren’t inherently “worst-case”
• Relationship between Big-Theta, Big-O and Big-Omega

$$f(n)\in \Theta (g(n))⟺f(n)\in O(g(n))\text{and}f(n)\in \Omega (g(n))$$

• Reflexivity of Big-Theta

$$f(n)\in \Theta (g(n))⟺g(n)\in \Theta (f(n))$$

little Notations

• little-o
  • Strict upper bound
  • $f(n)\in o(g(n))⟺\forall c>0,\exists n_0>0:f(n)<c\cdot g(n)\forall n\ge n_0$
• little-omega
  • Strict lower bound
  • $f(n)\in \omega (g(n))⟺\forall c>0,\exists n_0>0:c\cdot g(n)<f(n)\forall n\ge n_0$
• Relationships between Big and little notations

$$\begin{array}{c}o(g)\subseteq O(g)\\ \omega (g)\subseteq \Omega (g)\\ \\ f(n)\in o(g(n))⟹f(n)\in O(g(n))\\ f(n)\in \omega (g(n))⟹f(n)\in \Omega (g(n))\\ \\ o(f(n))\cap \omega (f(n))=\varphi \end{array}$$

Example with Asymptotic Notation

• Assume worst case time complexity of an algorithm
  • $T(n)=n^2+10n$
• Big-Omega
  • $T(n)\in \Omega (1),\Omega (n),\Omega (n\log n),\Omega (n^2)$
  • there are infinitely many lower bounds
• small-omega
  • $T(n)\in \omega (1),\omega (n),\omega (n\log n)$
  • there are infinitely many strict lower bounds
• Big-Theta
  • $T(n)\in \Theta (n^2)$
• Big-O
  • $T(n)\in O(n^2),O(n^3),O(2^n)$
  • there are infinitely many upper bounds
• small-o
  • $T(n)\in o(n^3),o(2^n)$
  • there are infinitely many strict upper bounds

Idea

• $o(g)$ = asymptotically strictly slower functions than $g$
• $O(g)$ = asymptotically slower + same rate functions as $g$
• $\Theta (g)$ = asymptotically same rate functions as $g$
• $\Omega (g)$ = asymptotically faster + same rate functions as $g$
• $\omega (g)$ = asymptotically faster functions than $g$
• Assume
  • $A<B$ : The functions represented by $B$ grow strictly faster than the functions represented by $A$
  • $A\le B$ : The functions represented by $B$ grow faster or same rate as functions represented by $A$
• Then

$$\begin{array}{r}o(g)<\Theta (g)<\omega (g)\\ \\ O(g)\le \Theta (g)\le \Omega (g)\end{array}$$

• Comparison of common complexities

$$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)$$

Complexity of Algorithms

• Running Time is denoted by $T(n)$
• Cases
  • Worst case
  • Average case
  • Best case
  • Amortized case
• Default convention
  • When asked for an algorithm’s complexity, we usually analyze its worst-case complexity
  • We commonly express it using Big-O notation, often intending the tightest asymptotic upper bound
• Why Big-O instead of Big-Theta?
  • Big-O is widely used as shorthand for algorithm complexity
  • Sometimes we cannot establish tight bound easily, hence Big-Theta cannot be used
  • When a tight bound is known, Big-Theta is perfectly valid and more informative

Average case complexity

• We can compute using Probability distribution

$$T_{\text{avg}}(n)=\sum _{i=1}^{m}P(x_i)T(x_i)$$

• Equal likely input case

$$T_{\text{avg}}(n)=\frac{1}{m}\sum _{i=1}^{m}T(x_i)$$

Amortized case complexity

• Very similar to equally likely average case
• Example:
  • $O(1)$ Time complexity for appending new element in dynamic array which internally performs resizing
• Is it defined for sequence of operations???
• How is it different from average case??