O(n)
Chapter 4 - Substitution Subtleties |
Document last modified: |
OVERVIEW
A correct bounds guess may not be close enough for the induction proof to hold.
The closed-end bounds guess can be changed by lower-order terms without changing the bounds:
n=O(n) and n-b = O(n) for any b
n2=O(n2) and n2-bn = O(n2) for any b
Note:
If f(n) ≤ cg(n), c > 0, ∀ n ≥ n0 then f(n) ∈ O(g(n)) f(n) ≤ cg(n)-b ≤ cg(n)
Example
Use the substitution method to show that T(n)
O(n)
where T(n) = 1 when n = 1 T(⌊n/2⌋) + T(⌈n/2⌉ ) + 1 when n > 1
Guess:
T(n) = O( n )
By definition of Big-O, must find c > 0 and n ≥ n0 > 0
0 ≤ T(n) ≤ cn
IH: T(⌊n/2⌋) ≤ c ⌊n/2⌋
T(⌈n/2⌉ )
≤ c ⌈n/2⌉
Induction Step:
| T(n) | = | T( ⌊n/2⌋ ) + T( ⌈n/2⌉ ) + 1 | Recurrence |
| ≤ | c ⌊n/2⌋ + c ⌈n/2⌉ + 1 | substitution of IH guess | |
| = | c ( ⌊n/2⌋ + ⌈n/2⌉ ) + 1 | ||
| = | cn + 1 | n = ⌊n/2⌋ + ⌈n/2⌉ | |
| ≤ | cn | fails |
Induction fails, because there is no constant c where c > 0 and n > 0:
cn + 1 ≤ cn
Try new guess by subtracting off a lower order term (b*n0 = b) from the old O(n) guess: T(n) ≤ cn
T(n) ≤
cn - b
IH: T( ⌊n/2⌋ ) ≤ c ⌊n/2⌋ - b
T( ⌈n/2⌉ ) ≤ c ⌈n/2⌉ - b
Show: T(n) ≤ cn - b
|
|
6. Base case: Find c and n0
Verify: T(n) ≤ cn - b
where T(n) = 1 when n = 1 T( ⌊n/2⌋ ) + T( ⌈n/2⌉ ) + 1 when n > 1 and cn - b solution for O(n)
Try n0 = 2 an even number
T( ⌊n/2⌋ ) + T( ⌈n/2⌉ ) + 1 ≤ cn - b T( ⌊2/2⌋ ) + T( ⌈2/2⌉ ) + 1 ≤ c(2)-b n0 = 2 T(1) + T(1) + 1 ≤ c(2)-b 1 + 1 + 1 ≤ c(2)-b b+3 ≤ 2c 2c ≥ b+3 b ≥ 1
2c ≥ 4 b = 1
c ≥ 2 holds for n0 = 2 and c ≥ 2
7. Choose: c ≥ 2 and n0 = 2
Since T(n) ≤ cn - b, ∀n ≥ n0 when b ≥ 1, c ≥ 2 and n0 = 2
T(n) ∈ O(n)
We can make that claim because:
T(n) ≤ cn - b ≤ cn for b ≥ 0
Note that n0 = 2 is the base case for induction, which we are free to choose, that establishes the boundary condition.
This is not the base case of the recurrence.
Example
Substitution method fails to show that T(n)
where T(n) = 1 when n = 1 4T(n/2) + n when n > 1
Guess:
T(n) = O(n2)
By definition of Big-O, must find c > 0 and n ≥ n0 > 0
0 ≤ T(n) ≤ cn2
IH: T(n/2) ≤ c(n/2)2
Induction Step:
T(n) = 4T(n/2) + n Recurrence ≤ 4c(n/2)2+ n substitution of IH = 4c(n2/4) + n = cn2 + n ≤ cn2 fails Induction fails, because must show exactly that:
T(n) ≤ cn2
T(n) = 1 when n = 1 4T(n/2) + n when n > 1
Guess: T(n) = O(n2)
Subtract off lower-order term n to make substitution work.
T(n) ≤ cn2 - bn
By definition of Big-O, must find c > 0 and n ≥ n0 > 0
IH: T(n/2) ≤ c(n/2)2 - bn/2
Induction Step:
T(n) = 4T(n/2) + n Recurrence ≤ 4[c(n/2)2 - bn/2] + n IH = 4cn2/4 - 4bn/2 + n = cn2 - 2bn + n ≤ cn2 - bn
Find constant b so the last two lines hold: cn2 - 2bn + n ≤ cn2 - bn
Solve for constant b:
cn2 - 2bn + n ≤ cn2 - bn -2bn + n ≤ -bn n ≤ bn b ≥ 1 By definition of Big-O, b > 0 is required
4. Base case: Find n0
Verify: T(n) ≤ cn2 - bn
where T(n) = 1 when n = 1 4T(n/2) + n when n > 1 and cn2 - bn solution for O(n2)
Try n0 = 2 an even number
4T(n/2) + n ≤ cn2 - bn 4T(2/2) + n ≤ c22 - b2 n0=2 4T(1) + 2 ≤ 4c-2b 4*1 + 2 ≤ 4c-2b 6 ≤ 4c-2b 2b+6 ≤ 4c 4c ≥ 2b+6 b ≥ 1
4c ≥ 8 b = 1
c ≥ 2 holds for n0 = 2 and c ≥ 2
5. Choose: c ≥ 2 and n0 = 2
Since T(n) ≤ cn2 - bn, ∀n ≥ n0 when b ≥ 1, c ≥ 2 and n0 = 2
T(n) ∈ O(n2)
Question 4.9.1
Show that substitution fails to demonstrate that T(n)
| 2 if n = 1
T(n) = |
| 9T(n/3) + n if n > 1O(n2): 0 ≤ T(n) ≤ cn2
IH: Assume holds for n/3, that is:
T(n/3) ≤ c(n/3)2 is true
Show: T(n) ≤ cn2
T(n) = 9T(n/3) + n ≤ = ≤ cn2
Recurrence IH substitution fails for c > 0
Question 4.9.2
Subtract a lower-order term and use substitution to show that T(n)
| 2 if n = 1
T(n) = |
| 9T(n/3) + n if n > 1O(n2): 0 ≤ T(n) ≤ cn2 - bn
IH: Assume holds for n/3, that is:
T(n/3) ≤ c(n/3)2 - bn/3 is true
Show: T(n) ≤ cn2 - bn
T(n) = 9T(n/3) + n ≤ = ≤ cn2 - bn which holds for c > 0 choosing b ≥ 1/2 Solve for b IH substitution
Base case: Find n0
Verify: T(n) ≤ cn2 - bn
where T(n) = 2 when n = 1 9T(n/3) + n when n > 1 and cn2 - bn solution for O(n2)
Try n0 = 3
9T(n/3) + n ≤ cn2 - bn 9T(3/3) + n ≤ c32 - b3 n0=3 ≤ ≥ b ≥ 1/2 ≥ b=1/2
c ≥ 2 1/2 holds for n0 = 3 and c ≥ 2 1/2
Question 4.10
Show that substitution fails to demonstrate that T(n)
| d if n = 1
T(n) = |
| 4T(⌊n/2⌋) + dn if n > 1O(n2): 0 ≤ T(n) ≤ cn2
IH: Assume holds for n/2, that is:
T(⌊n/2⌋) ≤ c(⌊n/2⌋)2 is true
Show: T(n) ≤ cn2
T(n) = 4T(⌊n/2⌋) + dn = ≤ = ≤ cn2
Recurrence IH substitution (⌊n/2⌋)2 ≤ (n/2)2 fails for c > 0
Substitution Subtlety
Subtract a lower-order term and use substitution to show that T(n)
| d if n = 1
T(n) = |
| 4T(⌊n/2⌋) + dn if n > 1O(n2): 0 ≤ T(n) ≤ cn2 - bn
IH: T(⌊n/2⌋) ≤ c(⌊n/2⌋)2 - b⌋n/2⌋
Show: T(n) ≤ cn2 - bn
T(n) = 4T(⌊n/2⌋) + dn ≤ 4( c(⌊n/2⌋)2 - b⌋n/2⌋ ) + dn ≤ 4( c(n/2)2 - bn/2 ) + dn = cn2 - 2bn + dn ≤ cn2 - bn which holds for c > 0 choosing b ≥ d Solve for b IH substitution
c, b, d > 0
-2bn + dn ≤ -bn
-bn + dn ≤ 0
dn ≤ bn
Base case: Find n0
Verify: T(n) ≤ cn2 - bn
where T(n) = d when n = 1 4T(⌊n/2⌋) + dn when n > 1 and cn2 - bn solution for O(n2)
Try n0 = 2 an even number
4T(⌊n/2⌋) + dn ≤ cn2 - bn 4T(⌊2/2⌋) + dn ≤ c22 - b2 n0=2 4T(1) + 2d ≤ 4c-2b 4*d + 2d ≤ 4c-2b 6d ≤ 4c-2b 2b+6d ≤ 4c 4c ≥ 2b+6d b ≥ d 4c ≥ 8d b=d
c ≥ 2d holds for n0 = 2 and c ≥ 2d
Question 4.10.1
Show that substitution fails to demonstrate that T(n)
where T(n) = 1 when n = 1 3T(n/2) + n when n > 1
Guess:
T(n) = O(nlg 3)
By definition of Big-O, must find c > 0 and n ≥ n0 > 0
0 ≤ T(n) ≤ cnlg 3
IH: T(n/2)
≤ c(n/2)lg 3
Induction Step:
| T(n) | = | 3T(n/2) + n | Recurrence |
| ≤ | substitution of IH | ||
| = | (x/y)lg 3 = xlg 3/ylg 3 | ||
| = | 2lg 3 = 3lg 2 = 3 | ||
| = | |||
| ≤ | cnlg 3 | fails |
Induction fails, because must show exactly that:
T(n) ≤ cnlg 3
Question 4.11.1
Subtract a lower-order term and use substitution to show that T(n)
where T(n) = 1 when n = 1 3T(n/2) + n when n > 1
Guess:
T(n) = O(nlg 3)
By definition of Big-O, must find c > 0 and n ≥ n0 > 0
0 ≤ T(n) ≤ cnlg 3 - bn
IH: T(n/2)
≤ c(n/2)lg 3 - bn/2
Induction Step:
| T(n) | = | 3T(n/2) + n | Recurrence |
| ≤ | substitution of IH | ||
| = | |||
| = | 2lg 3 = 3lg 2 = 3 | ||
| = | |||
| ≤ | cnlg 3 - bn/2 |
Verify: T(n) ≤ cnlg 3 - bn
| where T(n) = | 1 when n = 1 |
| 3T(n/2) + n when n > 1 |