Design and Analysis of Algorithms (DAA)

Asymptotic Analysis & Complexity Bounds

25 mins

Master the mathematical tools used to describe algorithm efficiency. Learn to differentiate Best, Worst, and Average cases using Linear Search, and deeply understand Big-O, Big-Omega, and Big-Theta notations.

Learning Goals

Differentiate between Best, Worst, and Average-case scenarios with practical examples.
Understand why the Worst-Case analysis is the industry standard.
Formally define and graph Big-O, Big-Omega, and Big-Theta asymptotic notations.
Apply these notations to calculate the upper and lower bounds of polynomial functions.

Understanding the Three Scenarios

When analyzing an algorithm theoretically, its performance usually depends heavily on the nature of the input, not just the size. Because of this, we categorize performance into three scenarios:

Best Case (Minimum Time): The input configuration that causes the algorithm to execute the absolute minimum number of operations. It is often unrealistic and not useful for practical guarantees.
Worst Case (Maximum Time): The input configuration that forces the algorithm to execute the maximum possible number of operations. This is the industry standard. It provides a critical mathematical guarantee that the algorithm will never take longer than this bound.
Average Case (Expected Time): The expected number of operations over all possible valid inputs, assuming a uniform probability distribution. It provides a realistic view of daily performance but is often mathematically difficult to compute.

Tracing Scenarios: The Linear Search Example

1
Step 1
Start at index 0. Compare $A[i]$ to $x$ . If they match, return i. If not, move to the next index. If the loop finishes without finding $x$ , return -1.
2
Step 2
Imagine we are searching for the number 5, and the array is [5, 8, 2, 9]. The algorithm finds the target on the very first comparison. It doesn't matter if the array has 4 elements or 4 million elements; it takes exactly 1 step. Time Complexity: $\Omega(1)$ (Constant time).
3
Step 3
Imagine we are searching for the number 9, or a number not in the array like 100. The algorithm must check every single element in the array from start to finish. If the array size is $n$ , it makes exactly $n$ comparisons. Time Complexity: $O(n)$ (Linear time).
4
Step 4
Assuming the target $x$ is somewhere in the array, on average, we will find it halfway through the array. It will take $n/2$ comparisons. In asymptotic analysis, we drop the constant $1/2$ . Time Complexity: $\Theta(n)$ (Linear time).

The 3 Asymptotic Notations

Asymptotic notations are mathematical tools used to represent the time and space complexity of algorithms as the input size $n$ approaches infinity.

1. Big-O ( $O$ ) Notation: Asymptotic Upper Bound

Big-O describes the worst-case scenario. It guarantees that the function will never grow faster than a specific rate.

Definition: $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that: $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$ .
Meaning: $f(n)$ is bounded above by $g(n)$ .

2. Big-Omega ( $\Omega$ ) Notation: Asymptotic Lower Bound

Big-Omega describes the best-case scenario. It guarantees that the function will take at least this much time.

Definition: $f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that: $0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$ .
Meaning: $f(n)$ is bounded below by $g(n)$ .

3. Big-Theta ( $\Theta$ ) Notation: Asymptotic Tight Bound

Big-Theta describes the average-case or exact bound. It means the algorithm grows at exactly the same rate as the bound.

Definition: $f(n) = \Theta(g(n))$ if there exist positive constants $c_1, c_2$ , and $n_0$ such that: $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$ .
Meaning: $f(n)$ is sandwiched perfectly between $c_1 \cdot g(n)$ and $c_2 \cdot g(n)$ .

Summary Table

Notation	Name	Bound Type	Use Case	Mathematical Condition
$O$	Big-O	Upper Bound	Worst-Case	$f(n) \le c \cdot g(n)$
$\Omega$	Big-Omega	Lower Bound	Best-Case	$f(n) \ge c \cdot g(n)$
$\Theta$	Big-Theta	Tight Bound	Average-Case	$c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$

Knowledge Check

Question 1 of 3

Q1Single choice

Which of the following notations is used to represent the worst-case time complexity of an algorithm?

O-notation

Ω-notation

Θ-notation

δ-notation

Asymptotic Notations Explained

web

Characteristics of Algorithms & Performance Measurements

Complexity Analysis and Time-Space Trade-offs