Different Notations Describe Bounds, Not Exact Running Time

Asymptotic notation bounds T(n), but it does not state its exact value

Consider the loop that adds every value in the array [4, 2, 7, 1]. The same loop can run on an array of any length n. For this lesson, its supplied operation-count function is T(n) = 3n + 2. When n = 4, the function gives T(4) = 14.

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += arr[i];
}

The expression T(n) = 3n + 2 gives a particular count for each input size. Asymptotic notation gives a different kind of statement: it describes a bound on that count as n grows. Saying T(n) is O(n), Omega(n), or Theta(n) does not replace T(n) with an exact equality.

Big O is an upper bound, and Omega is a lower bound

T(n) = 3n + 2 is O(n) because a constant multiple of n can stay above it from some point onward. For example, 4n is at least 3n + 2 whenever n is at least 2. The statement T(n) = O(n) therefore means that T(n) eventually does not exceed a constant multiple of n.

The same function is Omega(n) because another constant multiple of n can stay below it. For n at least 2, 2n is at most 3n + 2. The statement T(n) = Omega(n) means that T(n) eventually stays at or above a constant multiple of n.

Upper and lower describe the direction of an inequality, not the kind of input being discussed. Big O does not mean worst case, and Omega does not mean best case. If an algorithm has different counts for different inputs of the same size, those cases must be handled separately from the choice of bound notation.

Theta gives both bounds at once

For every n at least 2, the supplied function fits between two linear expressions: 2n <= 3n + 2 <= 4n. The left inequality gives an asymptotic lower bound, and the right inequality gives an asymptotic upper bound. Since both bounds are linear, T(n) = 3n + 2 is Theta(n).

Theta is a tight statement because it supplies both directions together. T(n) is also O(n^2), since a quadratic expression can eventually sit above this linear function, and it is also Omega(1), since it stays above a positive constant. Those statements are valid, but they leave out useful information that Theta(n) keeps.

A valid asymptotic bound may ignore finitely many small inputs

An asymptotic bound does not need to work for every positive input size. Choose c1 = 2 for the lower bound, c2 = 4 for the upper bound, and n0 = 2. For every n >= n0, the same function satisfies 2n <= T(n) <= 4n. Values before n0 do not invalidate the asymptotic statement.

The threshold matters because 4n is not above T(n) when n = 1: 4 is less than 5. From n = 2 onward, it is above the function, and 2n remains below it. Theta(n) records these two eventual bounds, not an exact count and not a promise that the inequalities begin at n = 1.