STEP-BY-STEP LESSON · §11.3
Application: Analysis of Algorithm Efficiency I
Choose a unit of work and count its repetitions.
Before you begin
Loop state and stopping condition
A loop repeats its body while a condition holds. Each assignment uses the current state; the order of updates affects later values. Distinguish executing the body from checking whether it should execute.
Finite sums
∑_{i=a}^{b}tᵢ adds tₐ,tₐ₊₁,…,t_b for integer bounds a≤b, including both endpoints. There are b−a+1 terms. A varying inner-loop count must be summed over the outer index.
Symbols
- T(n)
- number of selected operations for input size n
Definitions and notation for this topic
Big O, big Omega and big Theta
f∈O(g); f∈Ω(g); f∈Θ(g)
For eventually nonnegative functions f(n) and eventually positive g(n) on integer inputs: O(g) means f(n)≤C g(n) for all n≥n₀; Ω(g) means c g(n)≤f(n) for all n≥n₀; Θ(g) requires both bounds. Suitable constants c,C>0 and a threshold n₀ must exist and be independent of n.
Big O alone is an upper bound, not necessarily a tight order. The common shorthand f=O(g) means membership in a class of bounds, not equality with one function. Ω(g) is unrelated to the sample-space name Ω.
Separate glossary example
For n≥1, 3n²≤3n²+2n+1≤6n², so 3n²+2n+1∈Θ(n²), using c=3,C=6,n₀=1.
Operation count
T(n)
T(n) counts a specified kind of operation for inputs of size n. State the operation and whether the model describes a particular case, worst case or average case.
This is an exact count under that model; Θ(n²) describes its growth. It is not automatically a time in seconds or the count of every machine instruction.
Separate glossary example
If iteration i makes i−1 comparisons, for i=1,…,n, then T(n)=∑_{i=1}^{n}(i−1)=n(n−1)/2. For n=4 there are 6 comparisons.
Step by step
Step 1 / 6
Fix the size and operation
Size n may be an array length. Separately specify whether you count comparisons, assignments, or another operation.
Without a unit, “how much work” is ambiguous.
Worked example
For outer index i=1,…,n, an inner action repeats i times. Find the action count.
- The iterations perform 1,2,…,n actions.
- The sum is n(n+1)/2. For n=4, this is 1+2+3+4=10.
- With fixed cost per action, the total order is Θ(n²).
Optional self-check
For i=1,…,4 an action repeats i times. What changes if the inner action itself scans four entries?
Show answer
There are 1+2+3+4=10 inner executions, now with four entry visits each, giving 40 visits. Iteration count and work per iteration are separate.