1 of 46

Recurrences

CSE 332

2 of 46

Warm Up

Consider the following code:

public PriorityQueue fillHeap(List lst){

PriorityQueue pq = new MinHeap();

for(int i = 0; i < lst.size(); i++){

pq.insert(lst.get(i));

}

return pq;

}

What is the running time if the list is sorted in ascending order?

What is the running time if the list is sorted in descending order?

O(n)

O(nlog(n))

3 of 46

Recurrence Relations

4 of 46

Recurrence Relations

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

Generally in the form:

OR

“Divide & Conquer”

“Chip & Conquer”

5 of 46

Recurrence Relations

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

6 of 46

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(stack) with respect to input size

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:

7 of 46

Problem 0b

1 g(A, start, n) {

2 if n ≤ 10000 {

3 return 1000

4 }

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

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

7 println("Yay")

8 }

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

10 } else {

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

12 println("Yay")

13 }

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

15 }

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:

8 of 46

Tree Method Overview

9 of 46

Big Idea: T(n/b)

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

Asymptotically, these never matter!

we begin from i=0, so -1 to match the count

10 of 46

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

11 of 46

Q1(a) Tree Method Example

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

12 of 46

Solving the Summation

Q1(a) Tree Method Example

13 of 46

What Parts Matter?

Asymptotically Speaking

14 of 46

Q1(b) Base Case Doesn’t Matter!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

15 of 46

Solving the Summation

Q1(b) Base Case Doesn’t Matter!

16 of 46

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

…

17 of 46

Solving the Summation

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

18 of 46

Q1(d) Branching Factor (a) Matters!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

19 of 46

Solving the Summation

Q1(d) Branching Factor (a) Matters!

can move the n using the constant multiple rule

Geometric Series Sum Rule

simplification + props. of log & exponents:

multiplied by -2 and distributed our n

log rules:

20 of 46

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

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

21 of 46

Solving the Summation

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

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

can move the n using the constant multiple rule

22 of 46

Q1(f): Tree method

n

Work: 1

n-2

n-4

…

1

…

1

≈ n/2 levels

⇒ 2ⁱwork per level

1

#children

#levels

work

23 of 46

Q1(f): Solving the Summation

For a geometric series with a ratio < 1, it converges!

(Sum of a finite geometric series)

Note: formula like this will be provided for exams

24 of 46

Q1 (f) Reduction Constant (-b) Matters!

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!

25 of 46

Q1 Summary… What matters?

Base case, constants for f(n) do not matter…

Branching factor, reduction factor do matter!

Asymptotically, these never matter!

Asymptotically, these DO MATTER!

26 of 46

General Advice

27 of 46

Recursive Running Times - Guidance

OR

28 of 46

“Divide & Conquer”

29 of 46

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 /b cases highlighted in yellow

“Chip & Conquer”

30 of 46

Putting it All Together

31 of 46

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 }

32 of 46

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

33 of 46

Problem 2(b)

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

34 of 46

35 of 46

Our first call to T(n)

36 of 46

Our first call to T(n)

Input: n

37 of 46

Our first call to T(n)

Input: n

Work: c2*n + c1

38 of 46

Input: n/2

Input:

n/2

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

Input: n

Work: c2*n + c1

39 of 46

Input: n/2

Input: n

Work: c2*n + c1

40 of 46

Input: n/2

Work: c2*(n/2)+c1

Input: n/2

Work: c2*(n/2)+c1

Input: n

Work: c2*n + c1

41 of 46

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

42 of 46

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

43 of 46

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

44 of 46

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

45 of 46

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:

46 of 46

Thank You!