STEP-BY-STEP LESSON · §11.5
Application: Analysis of Algorithm Efficiency II
Relate shrinking a search region to step count.
Before you begin
Logarithms as exponents
For b>1 and n>0, log_b n is the unique exponent x with bˣ=n. For n≥1 and b>1, exactly ⌈log_b n⌉ repeated divisions by b are needed to first obtain a value at most 1. Halving specifically uses b=2 and log₂ n.
Count a specified operation
Name the unit being counted. Sequential blocks add their work. Nested loops multiply only when the inner count is the same on every outer iteration; otherwise sum the varying counts. Include work inside each body.
Symbols
- n/2ᵏ
- size after k halvings
- ⌈x⌉
- Least integer greater than or equal to real x
Definitions and notation for this topic
Floor and ceiling
⌊x⌋; ⌈x⌉
For real x, ⌊x⌋ is the greatest integer ≤x; ⌈x⌉ is the least integer ≥x.
The defining bounds are ⌊x⌋≤x<⌊x⌋+1 and ⌈x⌉−1<x≤⌈x⌉. Floor does not generally mean truncating toward zero.
Separate glossary example
⌊−2.3⌋=−3 and ⌈−2.3⌉=−2; for integer n, both ⌊n⌋ and ⌈n⌉ equal n.
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.
Logarithm and repeated halving
log_b x=y ⇔ b^y=x
For real b>0, b≠1 and x>0, log_b x is the exponent y for which b^y=x. In growth analysis the base is usually a fixed b>1.
Changing between fixed bases greater than 1 multiplies the logarithm by a positive constant. Actual algorithms may round sizes; include that rounding in an exact operation count.
Separate glossary example
log₂8=3. For n≥1, n/2^k≤1 exactly when k≥log₂n, so the least nonnegative integer k is ⌈log₂n⌉.
Step by step
Step 1 / 6
Describe size changes
In binary search on a sorted array, comparing with the middle retains only one half.
Sorted order makes discarding the other half valid.
Worked example
A region of 32 candidates is halved exactly at every step. How many reductions reach one candidate?
- The target is one remaining candidate, and each operation changes size from s to s/2.
- Sizes: 32→16→8→4→2→1.
- There are five reductions. This counts reductions, not necessarily exactly five comparisons in every search implementation.
Optional self-check
Starting at i=1, repeatedly double i while i<10. How many actions occur, and why is floor(log₂10) wrong?
Show answer
Actions occur at 1,2,4,8: four. The next value 16 reaches the stopping region. Rounding down to 3 stops at 8, which is still below 10.