Algorithmic Complexity: Time and Space

Algorithmic Complexity

• Measures the resources (time, space) an algorithm consumes.
• Focus on time complexity, which is the computer time needed for an algorithm to complete.
• Space complexity refers to the memory an algorithm requires to run.

Measuring Time Complexity

Experimental Analysis

• Involves implementing the algorithm.
• Running it with various input sizes and compositions.
• Measuring the running time using methods like System.currentTimeMillis().
• Plotting the results.

Theoretical Analysis

• Determines running time as a function of input size.
  • Input Size is problem-dependent.
    • Sorting: number of items.
    • Searching: number of items in search space.
    • Graph Problem: number of vertices/edges.
• Uses a high-level algorithm description.
• Considers all possible inputs, independent of hardware/software.

Primitive Operations

• These are basic computations independent of the environment
  • Expression evaluation.
  • Variable assignment.
  • Number comparison.
  • Method return.
• Primitive operations take constant time $O(1)$ in the worst case.

Counting Primitive Operations

• Number of operations executed by inspecting pseudo-code.
• $T(n) = 1 + n + 2(n-1) + 2(n-1) + 1 = 5n - 2$ in the example provided.
• Running time $T(n)$ is a linear function of $n$.

Growth Rate

• Changing environment affects running time by a constant factor.
• Linear growth rate of $T(n)$ remains unchanged, regardless of environment.
• Growth rate isn't affected by constant factors or lower-order terms.

Asymptotic Notation

• Focuses on the order of growth as input size increases.
• Big-O notation: $O(f(n))$.
• Big-Omega notation: $\Omega(f(n))$.
• Big-Theta notation: $\theta(f(n))$.

Big-O Notation

• $f(n)$ is $O(g(n))$ if there exist constants $c$ and $n_0$ such that $f(n) \le cg(n)$ for $n \ge n_0$.
• $f(n)$ grows no faster than $g(n)$.
• $2n + 10$ is $O(n)$ as $2n + 10 \le 3n$ for $n \ge 10$ (with $c = 3$ and $n_0 = 10$).

Big-Omega Notation

• $f(n)$ is $\Omega(g(n))$ if there exist constants $c$ and $n_0$ such that $f(n) \ge cg(n)$ for $n \ge n_0$.
• $f(n)$ grows at least as fast as $g(n)$.
• $2n + 10$ is $\Omega(n)$ as $2n + 10 \ge 2n$ for $n \ge 1$ (with $c = 2$ and $n_0 = 1$).

Big-Theta Notation

• $f(n)$ is $\theta(g(n))$ if there exist constants $c_1$, $c_2$, and $n_0$ such that $c_1g(n) \le f(n) \le c_2g(n)$ for $n \ge n_0$.
• $f(n)$ grows at the same rate as $g(n)$.
• $2n + 10$ is $\theta(n)$ as $2n \le 2n + 10 \le 3n$ for $n \ge 10$ (with $c_1 = 2$, $c_2 = 3$ and $n_0 = 10$).

Relationships Between $O$, $\Omega$, and $\theta$

• $f(n)$ is $\theta(g(n))$ if and only if $f(n)$ is $O(g(n))$ and $f(n)$ is $\Omega(g(n))$.

Properties of Asymptotic Notation

• Transitivity: If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(h(n))$, then $f(n)$ is $O(h(n))$.
• Similar transitivity properties hold for $\Omega$ and $\theta$.

Using Asymptotic Notation

• Big-O notation describes worst-case running time.
• Big-Omega notation describes best-case running time.
• Big-Theta notation describes average-case running time.

Common Growth Rates

• Constant: $\theta(1)$.
• Logarithmic: $\theta(log n)$.
• Linear: $\theta(n)$.
• N-Log-N: $\theta(n log n)$.
• Quadratic: $\theta(n^2)$.
• Cubic: $\theta(n^3)$.
• Exponential: $\theta(2^n)$.
• Factorial: $\theta(n!)$.