CSE 373 Section 3

Recurrence Party 🎉

​

(Grab a handout as you enter)

Agenda for Today

• Announcements
• Recurrences and their approaches
• Recap: What is a recurrence?
• Practice with recurrences
• Master Theorem
• Tree Method

Announcements

• P1 deadline extended to tonight!
• Hard deadline also extended to Sunday July 10 at 23:59
• P2 is out!
• 2 weeks to complete the assignment
• Due Wednesday July 20 at 23:59
• START EARLY!! 🕒
• Exercise 2 releases tomorrow
• Due Friday July 15 at 23:59
• Hard deadline July 18 at 23:59

​

Quick Reminder: Big-O Complexity

For simplification of mathematical expressions you can use Wolfram Alpha

If you’re unsure how the graph of a function looks like, desmos is your best friend!

Recurrences and their Approaches

Big Idea

Three* steps in solving for the runtime of a recursive function.

​

Model Code with Recurrence

Use Tree Method to Turn Recurrence into Summation.

Solve Summation for Closed Form

If Possible, Use Master Theorem for Tight Bound

Modeling Code with Recurrences?

​

What is a Recurrence?

An expression that lets us express the runtime of a function recursively.��

​

What is a Recurrence?

An expression that lets us express the runtime a function recursively.��

​

Base Case

​

Recursive Case

​

What is a Recurrence?

An expression that lets us express the runtime a function recursively.��

​

Base Case

​

Recursive Case

​

Recursive Call

Do Problems 1a + 3a Together!

​

​

Hint 2: You should use the answer from 1a to get 3a more quickly!

​

Hint 1: This is helpful for 1a (see “cheat-sheet” at end of PDF):

​

1a: Finding Bounds

1a: Finding Bounds

Outer loop runs N times

N

1a: Finding Bounds

The inner loop depends on the outer loop

N

1a: Finding Bounds

Inside the inner loop, we have a constant time operation

​

N

1a: Finding Bounds

Outer loop runs 0 ~ n - 1 times which defines i

Inner loop runs 0 ~ i - 1 times

As inner loop depends on the outer loop, we can express as the summation below.

N

N

Remember: Gauss’s identity

N

1a: Finding Bounds

​

POSSIBLE RUNTIME:

T(N) = N(N-1)/2 = ½ N² - ½ N

​

WORST CASE RUNTIME:

Θ(N²)

​

​

N²/2 + N/2 => N²

^{Best/worst cases agree!}

3a: Code To Recurrence

3a: Code To Recurrence

3a: Code To Recurrence

Base case when the input N <= 1

3a: Code To Recurrence

We saw the runtime for this loop earlier!

3a: Code To Recurrence

It’s N(N-1)/2!

(see Finding Bounds a)

3a: Code To Recurrence

Call f(N/2)

Constant addition

Call f(N/2)

Call f(N/2)

Call f(N/2)

3a: Code To Recurrence

Calling 4 functions and the input is divided by half each level

Work happening in both outer and inner loops

(see 1a)

3a: Code To Recurrence

Calling 4 functions and the input is divided by half each level

Work happening in both outer and inner loops

(see 1a)

Can also simplify non-recursive term (and only this term) using Big-O rules.

​

So you could also have put N² here.

3a: Code To Recurrence

Calling 4 functions and the input is divided by half each level

Work happening in both outer and inner loops

(see 1a)

Can also simplify non-recursive term (and only this term) using Big-O rules.

​

So you could also have put N² here.

In fact, you should simplify before doing Tree Method!

Shortcut: Master Theorem

Where are we?

Three* steps in solving for the runtime of a recursive function.

​

Model Code with Recurrence

Use Tree Method to Turn Recurrence into Summation.

Solve Summation for Closed Form

If Possible, Use Master Theorem for Tight Bound

Master Theorem: A “Cheat Code” (Kinda)

NOTE: If you get lucky and your recurrence matches the Master Theorem form, then you may use this formula to jump right to the final closed form.

​

(Of course, a lot of the time

it won’t match. That’s why tree method is still important.)

Master theorem wiki page

Use Master Theorem to find closed form

Original recurrence:

Step 1: Does T(n) match Master Theorem form?

a = 4

b = 2

e = 1

c = 2

Recall: could also have put N² here.

Use Master Theorem to find closed form

Original recurrence:

Step 2: Calculate log_b(a) and compare it to c

a = 4

b = 2

e = 1

c = 2

log_b(a) = log₂(4)

log₂(4) = 2

c = 2 so log_b(a) = c

log_b(a) = c so T(n) ∈ Θ(n²log n)

Ta-da!

4. Master Theorem

Use the cheat sheet attached to your section handout!

The Core Tree Method

Where are we?

Three* steps in solving for the runtime of a recursive function.

​

Model Code with Recurrence

Use Tree Method to Turn Recurrence into Summation.

Solve Summation for Closed Form

If Possible, Use Master Theorem for Tight Bound

Tree Method: Big Idea

This is a drawing approach that turns recurrences into summations.

​

Tree Method: Big Idea

This is a drawing approach that turns recurrences into summations.

​

i =0

i =1

i =2

i = 3

i = ???

Tree Method: Big Idea

This is a drawing approach that turns recurrences into summations.

​

i =0

i =1

i =2

i = 3

i = ???

Total Work:

Tree Method: Big Idea

This is a drawing approach that turns recurrences into summations.

​

i =0

i =1

i =2

i = 3

i = ???

But to actually compute this, there are multiple sub-questions we have to ask! ��(See Problem 5)

Total Work:

Problem 5a-g: Recurrence to Summation

The Tree

The Tree

The Tree

The Tree

5a: Input to a node at level i

We divide by 6 at each level, so the input at level i is n/6ⁱ.

5b: Work per node at (recursive) level i?

Same as the input to a node (in this case), so also n/6ⁱ.

5c: Number of nodes at level i

Each (non-base-case) node produces 3 more nodes, so at level i we have 3ⁱ nodes.

5d: Total work at the ith recursive level

(number of nodes in level) x (work per node at level)

5d: Total work at the ith recursive level

(number of nodes in level) x (work per node at level)

3ⁱ x n/6ⁱ

5e: Last Level of the Tree

We hit our base case when n/6ⁱ = 1.

5e: Last Level of the Tree

n/6ⁱ = 1

5e: Last Level of the Tree

n = 6ⁱ

5e: Last Level of the Tree

log₆(n) = i

5f: Total Work Done in the Base Case

(number of nodes in base case level) x (work per node in base case level)

5f: Total Work Done in the Base Case

(number of nodes in base case level) x (work per node in base case level)

5f: Total Work Done in the Base Case

(number of nodes in base case level) x (work per node in base case level)

5g: Total Work Summation

5g: Total Work Summation

Problem 5h: Getting the Closed Form

Where are we?

Three* steps in solving for the runtime of a recursive function.

​

Model Code with Recurrence

Use Tree Method to Turn Recurrence into Summation.

Solve Summation for Closed Form

If Possible, Use Master Theorem for Tight Bound

5h: Simplify to a closed form

Simplify the summation if possible (look for terms that can be pushed out of the summation)

Does this match any of our identities?

5h: Simplify to a closed form

5h: Simplify to a closed form

NOTE: You don’t have to simplify further, but if you were, you would get the following: (See section solutions for steps)

Problem 5i: Master Theorem

5i: Use Master Theorem to find closed form

Original recurrence:

Step 1: Does A(n) match Master Theorem form?

a = 3

b = 6

e = 1

c = 1

5i: Use Master Theorem to find closed form

Original recurrence:

Step 2: Calculate log_b(a) and compare it to c

a = 3

b = 6

e = 1

c = 1

log_b(a) = log₆(3)

log₆(3) = x

6^x = 3 so x < 1

c = 1 so x < c

log_b(a) < c so A(n) ∈ Θ(n)

Ta-da!