Solving Recurrence

Relations

So what does
T(n) = T(n-1) +n
look like anyway?

1
 Recurrence Relations

●A recurrence relation for the sequence {an} is an

equation that expresses an is terms of one or more of the
previous terms of the sequence, namely, a0, a1, …, an-1, for
all integers n with
n  n0, where n0 is a nonnegative integer.

●A sequence is called a solution of a recurrence relation if

it terms satisfy the recurrence relation.

2
 Recurrence Relations

●In other words, a recurrence relation is like a recursively

defined sequence, but without specifying any initial
values (initial conditions).

●Therefore, the same recurrence relation can have (and

usually has) multiple solutions.

●If both the initial conditions and the recurrence relation

are specified, then the sequence is uniquely determined.

3
 Recurrence Relations
●Example:
Consider the recurrence relation
an = 2an-1 – an-2 for n = 2, 3, 4, …

●Is the sequence {an} with an=3n a solution of this

recurrence relation?
●For n  2 we see that
2an-1 – an-2 = 2(3(n – 1)) – 3(n – 2) = 3n = an.
●Therefore, {an} with an=3n is a solution of the recurrence
relation.

4
 Recurrence Relations

●Is the sequence {an} with an=5 a solution of the same

recurrence relation?
●For n  2 we see that
2an-1 – an-2 = 25 - 5 = 5 = an.
●Therefore, {an} with an=5 is also a solution of the
recurrence relation.

5
 Modeling with Recurrence Relations

●Example:
●Someone deposits $10,000 in a savings account at a bank
yielding 5% per year with interest compounded annually.
How much money will be in the account after 30 years?
●Solution:
●Let Pn denote the amount in the account after n years.
●How can we determine Pn on the basis of Pn-1?

6
 Modeling with Recurrence Relations

●We can derive the following recurrence relation:

●Pn = Pn-1 + 0.05Pn-1 = 1.05Pn-1.
●The initial condition is P0 = 10,000.
●Then we have:
●P1 = 1.05P0
●P2 = 1.05P1 = (1.05)2P0
●P3 = 1.05P2 = (1.05)3P0
●…
●Pn = 1.05Pn-1 = (1.05)nP0

●We now have a formula to calculate Pn for 7any natural

number n and can avoid the iteration.
 Modeling with Recurrence Relations

●Let us use this formula to find P30 under the

●initial condition P0 = 10,000:

●P30 = (1.05)3010,000 = 43,219.42

●
After 30 years, the account contains $43,219.42.

8
 Recurrence Relations
● Can easily describe the runtime of recursive
algorithms
● Can then be expressed in a closed form (not
defined in terms of itself)

● Consider the linear search:

9
 Eg. 1 - Linear Search
● Recursively
● Look at an element (constant work, c), then
search the remaining elements…

• T(n) = T( n-1 ) + c
• “The cost of searching n elements is the
cost of looking at 1 element, plus the cost
of searching n-1 elements”
10
 Linear Seach (cont)

Caveat:
● You need to convince yourself (and others)
that the single step, examining an element,
*is* done in constant time.
● Can I get to the ith element in constant time,
either directly, or from the (i-1)th element?
● Look at the code

11
 Methods of Solving Recurrence
Relations
● Substitution
● Accounting method
● Draw the recursion tree, think about it
● The Master Theorem*
● Guess at an upper bound, prove it

12
 Linear Search (cont.)
● We’ll “unwind” a few of these
T(n) = T(n-1) + c (1)
But, T(n-1) = T(n-2) + c, from above
Substituting back in:
T(n) = T(n-2) + c + c
Gathering like terms
T(n) = T(n-2) + 2c (2)

13
 Linear Search (cont.)
● Keep going:
T(n) = T(n-2) + 2c
T(n-2) = T(n-3) + c
T(n) = T(n-3) + c + 2c
T(n) = T(n-3) + 3c (3)
● One more:
T(n) = T(n-4) + 4c (4)

14
 Looking for Patterns
● Note, the intermediate results are enumerated
● We need to pull out patterns, to write a general
expression for the kth unwinding
■ This requires practise. It is a little bit art. The
brain learns patterns, over time. Practise.
● Be careful while simplifying after substitution

15
 Eg. 1 – list of intermediates
Result at ith unwinding i

T(n) = T(n-1) + 1c 1

T(n) = T(n-2) + 2c 2

T(n) = T(n-3) + 3c 3

T(n) = T(n-4) + 4c 4

16
 Linear Search (cont.)
● An expression for the kth unwinding:
T(n) = T(n-k) + kc
● We have 2 variables, k and n, but we have a
relation
● T(d) is constant (can be determined) for some
constant d (we know the algorithm)
● Choose any convenient # to stop.

17
 Linear Search (cont.)
● Let’s decide to stop at T(0). When the list to
search is empty, you’re done…
● 0 is convenient, in this example…
Let n-k = 0 => n=k
● Now, substitute n in everywhere for k:
T(n) = T(n-n) + nc
T(n) = T(0) + nc = nc + c0 = O(n)
( T(0) is some constant, c0 )

18
 Binary Search

● Algorithm – “check middle, then search

lower ½ or upper ½”
● T(n) = T(n/2) + c
where c is some constant, the cost of checking the
middle…
● Can we really find the middle in constant
time? (Make sure.)

19
 Binary Search (cont)

Let’s do some quick substitutions:

T(n) = T(n/2) + c (1)
but T(n/2) = T(n/4) + c, so
T(n) = T(n/4) + c + c
T(n) = T(n/4) + 2c (2)
T(n/4) = T(n/8) + c
T(n) = T(n/8) + c + 2c
T(n) = T(n/8) + 3c (3)

20
 Binary Search (cont.)

Result at ith unwinding i

T(n) = T(n/2) + c 1

T(n) = T(n/4) + 2c 2

T(n) = T(n/8) + 3c 3

T(n) = T(n/16) + 4c 4
21
 Binary Search (cont)
● We need to write an expression for the k th
unwinding (in n & k)
■ Must find patterns, changes, as i=1, 2, …, k
■ This can be the hard part
■ Do not get discouraged! Try something else…
■ We’ll re-write those equations…
● We will then need to relate n and k

22
 Binary Search (cont)
Result at ith unwinding i

T(n) = T(n/2) + c =T(n/21) + 1c 1

T(n) = T(n/4) + 2c =T(n/22) + 2c 2

T(n) = T(n/8) + 3c =T(n/23) + 3c 3

T(n) = T(n/16) + 4c =T(n/24) + 4c 4

23
 Binary Search (cont)
● After k unwindings:
T(n) = T(n/2k) + kc
● Need a convenient place to stop unwinding –
need to relate k & n
● Let’s pick T(0) = c0 So,
n/2k = 0 =>
n=0
Hmm. Easy, but not real useful…

24
 Binary Search (cont)

● Okay, let’s consider T(1) = c 0

● So, let:
n/2k = 1 =>
n = 2k =>
k = log2n = lg n

25
 Binary Search (cont.)
● Substituting back in (getting rid of k):
T(n) = T(1) + c lg(n)
= c lg(n) + c0
= O( lg(n) )

26
 Review: Solving Recurrences
● The substitution method
■ A.k.a. the “making a good guess method”
■ Guess the form of the answer, then use induction to
find the constants and show that solution works
■ Run an example: merge sort
○ T(n) = 2T(n/2) + cn
○ We guess that the answer is O(n lg n)
○ Prove it by induction
■ Can similarly show T(n) = Ω(n lg n), thus Θ(n lg n)
 Review: Solving Recurrences
● The “iteration method”
■ Expand the recurrence
■ Work some algebra to express as a summation
■ Evaluate the summation
● We showed several examples, were in the middle of:

 c n 1
  n
T (n) aT
   cn n  1
  b 
  c n 1
  n
T (n) aT
   cn n  1
  b 
● T(n) =
aT(n/b) + cn
a(aT(n/b/b) + cn/b) + cn
a2T(n/b2) + cna/b + cn
a2T(n/b2) + cn(a/b + 1)
a2(aT(n/b2/b) + cn/b2) + cn(a/b + 1)
a3T(n/b3) + cn(a2/b2) + cn(a/b + 1)
a3T(n/b3) + cn(a2/b2 + a/b + 1)
…
akT(n/bk) + cn(ak-1/bk-1 + ak-2/bk-2 + … + a2/b2 + a/b + 1)
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So we have
■ T(n) = akT(n/bk) + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)

● For k = logb n
■ n = bk
■ T(n) = akT(1) + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)
= akc + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)
= cak + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)
= cnak /bk + cn(ak-1/bk-1 + ... + a2/b2 + a/b + 1)
= cn(ak/bk + ... + a2/b2 + a/b + 1)
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a = b?
■ T(n) = cn(k + 1)
= cn(logb n + 1)
= (n log n)
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a < b?
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a < b?
■ Recall that (xk + xk-1 + … + x + 1) = (xk+1 -1)/(x-1)
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a < b?
■ Recall that (xk + xk-1 + … + x + 1) = (xk+1 -1)/(x-1)
■ So:
ak ak1 a
 k 1   1 
a b k 1  1 
1  a b 
k 1

1
k
b b b a b   1 1  a b  1 a b
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a < b?
■ Recall that (xk + xk-1 + … + x + 1) = (xk+1 -1)/(x-1)
■ So:
ak ak1 a
 k 1   1 
a b k 1  1 
1  a b 
k 1

1
k
b b b a b   1 1  a b  1 a b

■ T(n) = cn ·(1) = (n)

  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a > b?
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a > b?
k
a a k1
a
 k1   1 
a b k 1  1 
  a b 
k

k
b b b a b   1
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a > b?
k
a a k1
a
 k1   1 
a b k 1  1 
  a b 
k

k
b b b a b   1
■ T(n) = cn · (ak / bk)
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a > b?
k
a a k1
a
 k1   1 
a b k 1  1 
  a b 
k

k
b b b a b   1
■ T(n) = cn · (ak / bk)
= cn · (alog n / blog n) = cn · (alog n / n)
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a > b?
k
a a k1
a
 k1   1 
a b k 1  1 
  a b 
k

k
b b b a b   1
■ T(n) = cn · (ak / bk)
= cn · (alog n / blog n) = cn · (alog n / n)
recall logarithm fact: alog n = nlog a
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a > b?
a k a k1
   
a
 1 
a b  1
k 1
  a 
b k

bk bk1 b a b   1
■ T(n) = cn · (a / b )
k k

= cn · (alog n / blog n) = cn · (alog n / n)

recall logarithm fact: alog n = nlog a
= cn · (nlog a / n) = (cn · nlog a / n)
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So with k = logb n
■ T(n) = cn(ak/bk + ... + a2/b2 + a/b + 1)
● What if a > b?
a k a k1
   
a
 1 
a b  1
k 1
  a 
b k

bk bk1 b a b   1
■ T(n) = cn · (a / b )
k k

= cn · (alog n / blog n) = cn · (alog n / n)

recall logarithm fact: alog n = nlog a
= cn · (nlog a / n) = (cn · nlog a / n)
= (nlog a )
  c n 1
  n
T (n) aT
   cn n  1
  b 
● So…

 n  a b

T (n) n log b n  a b

  n logb a
  a b
 The Master Theorem
● Given: a divide and conquer algorithm
■ An algorithm that divides the problem of size n
into a subproblems, each of size n/b
■ Let the cost of each stage (i.e., the work to divide
the problem + combine solved subproblems) be
described by the function f(n)
● Then, the Master Theorem gives us a
cookbook for the algorithm’s running time:
 The Master Theorem
● if T(n) = aT(n/b) + f(n) then

 

  
n 
logb a
 
f (n) O n logb a   

 
   0
T (n)  n  logb a
log n  f (n)  n 
logb a

  c 1
 
 f (n)   
f (n)  n logb a  AND 
 
 af (n / b)  cf (n) for large n
 Using The Master Method
● T(n) = 9T(n/3) + n
■ a=9, b=3, f(n) = n
■ nlog a = nlog
b
= (n2)
3 9

■ Since f(n) = O(nlog 9 - ), where =1, case 1 applies:

3

  
T (n)  n logb a when f (n) O n logb a   
■ Thus the solution is T(n) = (n2)
 Quiz
● Solve - 3T(n/2)+n2