5.3 Counting Steps and Asymptotic Growth

Section 5.2 proved whether an algorithm is correct. Correctness is essential, but it does not tell us whether an algorithm remains practical when its input becomes large.

Suppose two correct search procedures require

20n \qquad\text{and}\qquad n^2

basic operations on an input of size $n$ . At $n=5$ , the second expression is smaller:

20(5)=100,\qquad 5^2=25.

At $n=100$ , the comparison reverses:

20(100)=2000,\qquad100^2=10000.

To understand scalability, we study how required work grows with input size.

Input size and a cost model

The input size is a number describing how much input an algorithm receives. We usually denote it by $n$ .

Examples:

for an array, $n$ may be its number of elements;

for a graph, size may involve both vertices and edges;

for an integer, size may mean its number of binary digits rather than its numerical value.

In this section, the meaning of $n$ will always be stated.

A cost model chooses which basic operations to count. Examples include comparisons, assignments, arithmetic operations, or array accesses.

The count is a mathematical model, not a stopwatch measurement. Real machines differ in processor speed, language, compiler, and memory behavior. Counting operations lets us compare algorithms independently of those details.

Counting a straight-line procedure

Consider:

text

x ← a + b
y ← x × 2
return y

If we count arithmetic operations and assignments, a possible model gives:

one addition;

one assignment to $x$ ;

one multiplication;

one assignment to $y$ .

The total is $4$ , independent of input size. Different reasonable models may count the return or treat an arithmetic assignment as one combined operation. The exact constant changes, but the absence of growth does not.

Counting one loop

Consider:

text

total ← 0
for i ← 1 to n
    total ← total + A[i]
return total

If we count only executions of the addition in the loop body, the exact count is

T(n)=n.

If we count one initialization, $n$ additions, $n$ assignments to $total$ , and one return, then

T(n)=1+n+n+1=2n+2.

The cost model changes the exact formula, but both formulas grow proportionally to $n$ .

Sequential blocks add

If one loop runs $n$ times and a later loop runs $3n$ times, the total number of body executions is

n+3n=4n.

Sequential work adds because the second block runs after the first.

Nested loops multiply

Consider:

text

for i ← 1 to n
    for j ← 1 to n
        output (i, j)

For each of the $n$ values of $i$ , the inner loop uses all $n$ values of $j$ . Therefore the output executes

\underbrace{n+n+\cdots+n}_{n\text{ copies}}=n^2

times.

The iterations correspond to the Cartesian product

\{1,\ldots,n\}\times\{1,\ldots,n\},

connecting this count to Chapter 1.

Not every nested loop is $n^2$ . If the inner loop runs only from $1$ through $i$ , the count is

1+2+\cdots+n =\sum_{i=1}^{n}i =\frac{n(n+1)}{2}.

This is still quadratic growth, but the exact number is roughly half of $n^2$ .

A loop that repeatedly halves

Consider:

text

x ← n
while x > 1
    x ← floor(x / 2)

After $k$ iterations, $x$ is approximately

\frac{n}{2^k}.

The loop stops when this value reaches $1$ . Solving

\frac{n}{2^k}\le1

gives

n\le2^k \qquad\Longrightarrow\qquad k\ge\log_2 n.

The number of iterations is

\lfloor\log_2 n\rfloor

for many common loop conventions, up to a small endpoint adjustment. The important fact is logarithmic growth: doubling $n$ adds about one more iteration.

Loading interactive lab...

Run single, sequential, nested, triangular, and halving loops under a live operation counter. Change $n$ , step through highlighted executions, and compare the observed trace against an exact symbolic count you assemble from visual iteration regions.

Loading concept check...

Loading practice...

Best-case and worst-case input behavior

The same input size may produce different costs.

For linear search on an array of length $n$ :

if the target is at index $0$ , one comparison is enough;

if the target is absent or appears only at index $n-1$ , the algorithm makes $n$ comparisons.

Therefore:

T_{\mathrm{best}}(n)=1, \qquad T_{\mathrm{worst}}(n)=n.

Whenever we state a complexity, we should identify whether it describes the best case, worst case, or another specified situation. In this course, an unqualified upper-bound analysis usually refers to the worst case.

Why exact formulas are sometimes more detail than we need

Suppose one implementation uses

T_1(n)=3n^2+10n+7,

while another uses

T_2(n)=50n^2+2.

Their exact counts differ. Yet both are dominated by a constant multiple of $n^2$ for large $n$ . The quadratic term eventually grows faster than the linear and constant terms.

Asymptotic analysis describes this long-run growth while ignoring constant factors and lower-order terms.

Big-O gives an eventual upper bound

We write

f(n)\in O(g(n))

if there exist constants $c>0$ and $n_0$ such that

0\le f(n)\le c\,g(n)

for every $n\ge n_0$ .

The constants $c$ and $n_0$ are witnesses. The inequality need not hold for every small input; it must hold from some threshold onward.

Example: proving a quadratic upper bound

Let

f(n)=3n^2+10n+7.

For $n\ge1$ ,

10n\le10n^2 \qquad\text{and}\qquad 7\le7n^2.

Therefore

f(n) \le3n^2+10n^2+7n^2 =20n^2.

Choosing $c=20$ and $n_0=1$ proves

f(n)\in O(n^2).

Big-O is an upper bound, not automatically a tight description. Because $n\le n^2$ for $n\ge1$ , a linear function also belongs to $O(n^2)$ . To say “grows exactly at this order,” we need matching upper and lower bounds.

Big-Omega gives an eventual lower bound

We write

f(n)\in\Omega(g(n))

if there exist constants $c>0$ and $n_0$ such that

0\le c\,g(n)\le f(n)

for every $n\ge n_0$ .

For $f(n)=3n^2+10n+7$ and $n\ge1$ ,

3n^2\le f(n),

so $f(n)\in\Omega(n^2)$ with $c=3$ .

Big-Theta gives a tight growth rate

We write

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

when both

f(n)\in O(g(n)) \qquad\text{and}\qquad f(n)\in\Omega(g(n)).

Equivalently, there are positive constants $c_1,c_2,n_0$ such that

0\le c_1g(n)\le f(n)\le c_2g(n)

for every $n\ge n_0$ .

Our two bounds prove

3n^2+10n+7\in\Theta(n^2).

Common growth families

From slower to faster, common nonnegative growth rates are:

1 \prec \log n \prec n \prec n\log n \prec n^2 \prec n^3 \prec 2^n \prec n!.

Here $\prec$ informally means “eventually grows more slowly than.” It is not the partial-order relation from Chapter 4, though both express comparison.

The gaps become dramatic. At $n=20$ :

n^2=400, \qquad 2^n=1{,}048{,}576, \qquad n!=2{,}432{,}902{,}008{,}176{,}640{,}000.

Constants still matter for real workloads, especially for small inputs. Asymptotic growth answers a different question: what happens as input size continues to increase?

Loading interactive lab...

Launch functions with adjustable constant factors into a logarithmic growth race. Move the input-size horizon, inspect crossover points, and fit upper and lower envelopes to distinguish loose Big-O claims from tight Big-Theta classifications.

Loading concept check...

Loading practice...

Note

Big-O does not mean “equal to” or “the worst case” by itself. It is an eventual upper-bound relationship. State the input situation separately, and use Big-Theta when both upper and lower bounds match.

Chapter bridge

Chapter 5 connected procedures with mathematics. We specified algorithms using pseudocode, proved correctness with invariants and termination measures, counted exact operations, and classified long-run growth.

Chapter 6 develops systematic counting principles. Those tools will let us count choices without listing every outcome—and will also explain why nested loops, search spaces, and combinatorial algorithms can grow so quickly.

5.3 Counting Steps and Asymptotic Growth

Section 5.2 proved whether an algorithm is correct. Correctness is essential, but it does not tell us whether an algorithm remains practical when its input becomes large.

Suppose two correct search procedures require

20n \qquad\text{and}\qquad n^2

basic operations on an input of size $n$ . At $n=5$ , the second expression is smaller:

20(5)=100,\qquad 5^2=25.

At $n=100$ , the comparison reverses:

20(100)=2000,\qquad100^2=10000.

To understand scalability, we study how required work grows with input size.

Input size and a cost model

The input size is a number describing how much input an algorithm receives. We usually denote it by $n$ .

Examples:

for an array, $n$ may be its number of elements;

for a graph, size may involve both vertices and edges;

for an integer, size may mean its number of binary digits rather than its numerical value.

In this section, the meaning of $n$ will always be stated.

A cost model chooses which basic operations to count. Examples include comparisons, assignments, arithmetic operations, or array accesses.

Counting a straight-line procedure

Consider:

text

x ← a + b
y ← x × 2
return y

If we count arithmetic operations and assignments, a possible model gives:

one addition;

one assignment to $x$ ;

one multiplication;

one assignment to $y$ .

Counting one loop

Consider:

text

total ← 0
for i ← 1 to n
    total ← total + A[i]
return total

If we count only executions of the addition in the loop body, the exact count is

T(n)=n.

If we count one initialization, $n$ additions, $n$ assignments to $total$ , and one return, then

T(n)=1+n+n+1=2n+2.

The cost model changes the exact formula, but both formulas grow proportionally to $n$ .

Sequential blocks add

If one loop runs $n$ times and a later loop runs $3n$ times, the total number of body executions is

n+3n=4n.

Sequential work adds because the second block runs after the first.

Nested loops multiply

Consider:

text

for i ← 1 to n
    for j ← 1 to n
        output (i, j)

For each of the $n$ values of $i$ , the inner loop uses all $n$ values of $j$ . Therefore the output executes

\underbrace{n+n+\cdots+n}_{n\text{ copies}}=n^2

times.

The iterations correspond to the Cartesian product

\{1,\ldots,n\}\times\{1,\ldots,n\},

connecting this count to Chapter 1.

Not every nested loop is $n^2$ . If the inner loop runs only from $1$ through $i$ , the count is

1+2+\cdots+n =\sum_{i=1}^{n}i =\frac{n(n+1)}{2}.

This is still quadratic growth, but the exact number is roughly half of $n^2$ .

A loop that repeatedly halves

Consider:

text

x ← n
while x > 1
    x ← floor(x / 2)

After $k$ iterations, $x$ is approximately

\frac{n}{2^k}.

The loop stops when this value reaches $1$ . Solving

\frac{n}{2^k}\le1

gives

n\le2^k \qquad\Longrightarrow\qquad k\ge\log_2 n.

The number of iterations is

\lfloor\log_2 n\rfloor

for many common loop conventions, up to a small endpoint adjustment. The important fact is logarithmic growth: doubling $n$ adds about one more iteration.

Loading interactive lab...

Loading concept check...

Loading practice...

Best-case and worst-case input behavior

The same input size may produce different costs.

For linear search on an array of length $n$ :

if the target is at index $0$ , one comparison is enough;

if the target is absent or appears only at index $n-1$ , the algorithm makes $n$ comparisons.

Therefore:

T_{\mathrm{best}}(n)=1, \qquad T_{\mathrm{worst}}(n)=n.

Why exact formulas are sometimes more detail than we need

Suppose one implementation uses

T_1(n)=3n^2+10n+7,

while another uses

T_2(n)=50n^2+2.

Their exact counts differ. Yet both are dominated by a constant multiple of $n^2$ for large $n$ . The quadratic term eventually grows faster than the linear and constant terms.

Asymptotic analysis describes this long-run growth while ignoring constant factors and lower-order terms.

Big-O gives an eventual upper bound

We write

f(n)\in O(g(n))

if there exist constants $c>0$ and $n_0$ such that

0\le f(n)\le c\,g(n)

for every $n\ge n_0$ .

The constants $c$ and $n_0$ are witnesses. The inequality need not hold for every small input; it must hold from some threshold onward.

Example: proving a quadratic upper bound

Let

f(n)=3n^2+10n+7.

For $n\ge1$ ,

10n\le10n^2 \qquad\text{and}\qquad 7\le7n^2.

Therefore

f(n) \le3n^2+10n^2+7n^2 =20n^2.

Choosing $c=20$ and $n_0=1$ proves

f(n)\in O(n^2).

Big-Omega gives an eventual lower bound

We write

f(n)\in\Omega(g(n))

if there exist constants $c>0$ and $n_0$ such that

0\le c\,g(n)\le f(n)

for every $n\ge n_0$ .

For $f(n)=3n^2+10n+7$ and $n\ge1$ ,

3n^2\le f(n),

so $f(n)\in\Omega(n^2)$ with $c=3$ .

Big-Theta gives a tight growth rate

We write

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

when both

f(n)\in O(g(n)) \qquad\text{and}\qquad f(n)\in\Omega(g(n)).

Equivalently, there are positive constants $c_1,c_2,n_0$ such that

0\le c_1g(n)\le f(n)\le c_2g(n)

for every $n\ge n_0$ .

Our two bounds prove

3n^2+10n+7\in\Theta(n^2).

Common growth families

From slower to faster, common nonnegative growth rates are:

1 \prec \log n \prec n \prec n\log n \prec n^2 \prec n^3 \prec 2^n \prec n!.

Here $\prec$ informally means “eventually grows more slowly than.” It is not the partial-order relation from Chapter 4, though both express comparison.

The gaps become dramatic. At $n=20$ :

n^2=400, \qquad 2^n=1{,}048{,}576, \qquad n!=2{,}432{,}902{,}008{,}176{,}640{,}000.

Constants still matter for real workloads, especially for small inputs. Asymptotic growth answers a different question: what happens as input size continues to increase?

Loading interactive lab...

Loading concept check...

Loading practice...

Note