1 of 44

Recurrences

CSE 332 - Section 3

2 of 44

Part 1: Recurrence Relations

3 of 44

Recurrence Relations Overview

Describes the time complexity of recursive algorithms, often uses T(n)

Same way that f(n) and g(n) described time complexity of non recursive algorithms last week

Generally in the form:

OR

“Divide & Conquer”

“Chip & Conquer”

4 of 44

Recurrence Relations Examples

n = input size
T(n) = runtime for input size n
b = how input shrinks for next recursive call(s) (reduction factor/ constant)
a = number of recursive calls made per function call (branching factor)

foo(L) { // n = L.size

if (L.size <= 1) {

return 1;

}

L.remove(0); // n = n-1

return foo(L) + foo(L);

}

a = 2

b = 1

OR

bar(A, start, n) {

if (n-start <= 1) {

return 1;

}

return 2*bar(A, start, n/2);

}

a = 1

b = 2

5 of 44

Problem 0a

1 f(stack) { // stack.size = n

2 if (stack.size == 0) {

3 return 0

4 }

5 stack.pop // stack.size --

6 return 2*f(stack)+1

7 }

Find a recurrence T(n) modelling the worst-case runtime complexity of f(n)

When does the base case occur?
What is the branching factor a?
What is the reduction factor / b?
What is the amount of non-recursive work f(n)?

n ≤ 0

?

a = 1 since we only make one recursive call

b = 1 since we always reduce input size by 1

constant

constant, which we can denote as c₁

Recurrence relation forms:

6 of 44

Problem 0b

1 g(A, start, n) {

2 if n ≤ 10000 {

3 return 1000

4 }

5

6 if (g(A, start, n/3) > 5) {

7 for (int i=0; i<n; i++) {

8 println("Yay")

9 }

10 return 5*g(A, start, n/3)

11 } else {

12 for (int i=0; i<n*n; i++) {

13 println("Yay")

14 }

15 return 4*g(A, start, n/3)

16 }

Find a recurrence T(n) modelling the worst-case runtime complexity of f(n)

When does the base case occur?
What is the branching factor a?
What is the reduction factor /b?
What is the amount of non-recursive work f(n)?

n ≤ 10000

a = 2

b = 3

c1*n + c2

Recurrence relation forms:

7 of 44

Tree Method Overview

8 of 44

Big Idea: T(n/b)

…

c

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

Asymptotically, these never matter!

9 of 44

Big Idea: T(n - b)

Red box represents a problem instance

Blue value represents time spent at that level of recursion

n

f(n)

n - b

n - 2b

…

x

…

x

f(n-b)

f(n-2b)

c

≈ n/b levels

Asymptotically, these never matter!

⇒ aⁱ f(n - bi)

work per level

10 of 44

Q1(a) Tree Method Example

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

11 of 44

Q1(a) Solving the Summation

12 of 44

Your Turn!

Try problems 1b-1f

13 of 44

Q1(b) Base Case Doesn’t Matter!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

14 of 44

Q1(b) Solving the Summation

15 of 44

Q1(c) Constants for f(n) Don’t Matter!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

16 of 44

Q(1c) Solving the Summation

17 of 44

Q1(d) Branching Factor (a) Matters!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

18 of 44

Q(1d) Solving the Summation

can move the n using the constant multiple rule

multiplied by -2 and distributed our n

19 of 44

Q1(e) Reduction Factor (/b) Does Matter!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

20 of 44

Q(1e) Solving the Summation

can move the n using the constant multiple rule

This is a geometric series with a ratio < 1, so it converges to a constant!

21 of 44

Q1(f): Tree method

n

Work: 1

n-2

n-4

…

1

…

1

≈ n/2 levels

⇒ 2ⁱwork per level

#children

#levels

work

22 of 44

Q1(f): Solving the Summation

Note: formula like this will be provided for exams

23 of 44

Reduction Constant (-b) Matters!

1

Left/top represents -1 case

Right/bottom represents -2 case

n

1

n-1 or n-2

n-2 or n-4

…

1

…

1

≈ n levels for -1

≈ n/2 levels for -2

⇒ 2ⁱ

work per level for both cases

Hint: Use the Finite Geometric Series (#7 on Math Identities) to solve these summations!

24 of 44

General Advice

25 of 44

Recursive Running Times - Guidance

26 of 44

27 of 44

Draw a tree such that:

Each node has a children
The “size of each node is b less than the size of its parent
The “work” for each node is f applied to its size
The height of the tree is n/b

Sum the tree horizontally

I.e. identify the total work done at each level

Sum the levels’ work vertically

Given the sum of all work in the entire tree

Only differences between divide and conquer cases highlighted in yellow

28 of 44

Putting it All Together

29 of 44

Problem 2(a)

(a) Find a recurrence T(n) modeling the worst-case runtime complexity of f(n).

1 f(L, start, n) {

2 if (n - start <= 1) {

3 return 0

4 }

5 int res = f(L, start, n/2)

6 for (int i=0; i<n; i++) {

7 result *= 4

8 }

9 return res + f(L, start, n/2)

10 }

1 f(L, start, j) { //n = j - start

2 if (j - start <= 1) {

3 return 0

4 }

5 int res = f(L, start, n/2)

6 for (int i=0; i<j; i++) {

7 result *= 4

8 }

9 return res + f(L, start, j/2)

10 }

30 of 44

Problem 2(a)

(a) Find a recurrence T(n) modeling the worst-case runtime complexity of f(n).

1 f(L, start, j) { //n = j - start

2 if (j - start <= 1) {

3 return 0

4 }

5 int res = f(L, start, n/2)

6 for (int i=0; i<j; i++) {

7 result *= 4

8 }

9 return res + f(L, start, j/2)

10 }

2 function calls -> a = 2
Reducing input size by half -> (n / 2)
Non-recursive work has loop with n iterations and some constant work -> f(n) = c_2n + c_1

31 of 44

Problem 2(b)

(b) Find a closed form to your answer for (a).

32 of 44

33 of 44

Our first call to T(n)

34 of 44

Our first call to T(n)

Input: n

35 of 44

Our first call to T(n)

Input: n

Work: c2*n + c1

36 of 44

Input: n/2

Input:

n/2

“2T(...)” = 2 recursive calls

Input: n

Work: c2*n + c1

37 of 44

Input: n/2

Input: n

Work: c2*n + c1

38 of 44

Input: n/2

Work: c2*(n/2)+c1

Input: n/2

Work: c2*(n/2)+c1

Input: n

Work: c2*n + c1

39 of 44

Input: n/2

Work: c2*(n/2)+c1

Input: n/2

Work: c2*(n/2)+c1

Input: n/4

Input: n

Work: c2*n + c1

40 of 44

Input: n/2

Work: c2*(n/2)+c1

Input: n/2

Work: c2*(n/2)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n

Work: c2*n + c1

41 of 44

Input: n/2

Work: c2*(n/2)+c1

Input: n/2

Work: c2*(n/2)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n

Work: c2*n + c1

Input: 1

42 of 44

Input: n/2

Work: c2*(n/2)+c1

Input: n/2

Work: c2*(n/2)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n

Work: c2*n + c1

Input: 1

Work: c0

Input: 1

Work: c0

Input: 1

Work: c0

Input: 1

Work: c0

43 of 44

Input: n/2

Work: c2*(n/2)+c1

Input: n/2

Work: c2*(n/2)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n/4

Work: c2*(n/4)+c1

Input: n

Work: c2*n + c1

Input: 1

Work: c0

Input: 1

Work: c0

Input: 1

Work: c0

Input: 1

Work: c0

Since we’re in /b case:

With a, b, and f(n) plugged in:

44 of 44

Thank You!