CSE 373 SP25 Week 3 AX

Recurrences and Deques Practice

Micro-Teach: Recurrences

Big Idea

Two steps:

1. Code to Recurrence:

Model recursive code with recurrence

1. Recurrence to Big-Theta:

Unroll the recurrence equation, or Tree Method

Goal: Analyze the runtime of some recursive code

Resource Slide: Partial Sums to Know

1 + ½ + ¼ + ⅛ + … + 1/N = 2 ∈ Θ(2)

1 + 2 + 3 + 4 + ⋯ + N = (N² + N) / 2 ∈ Θ(N²)

1 + 2 + 4 + 8 + ⋯ + N = 2N - 1 ∈ Θ(N)

​

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?

Base Case

​

Recursive Case

​

Recursive Call

Recurrence Diagram: Format

RECURSIVE WORK

T(N) = size of current

subproblem

T(N) = size of current subproblem

(in recursive call)

T(N) = size of current

subproblem

(in recursive call)

~ NON-RECURSIVE WORK

(for subproblem)

~ non-recursive work

(for subproblem)

~ non-recursive work

(for subproblem)

T(N)

T(N)

T(N)

T(N)

. . .

. . .

~ non-recursive

~ non-recursive

~ non-recursive

~ non-recursive

Example 2: Binary Search

N

N/2

N/4

1

~1

~1

~1

~1

Coefficient.

1 branch for one recursive call.

Non-recursive work (constant)

​

​

…

Recursive work.

​

Recurrence: T(N) = T(N/2) + 1

Tree/Diagram Method.

[Step 1] What's the non-recursive work per level?

• 1 — for the i^th level

​

[Step 2] How many total levels are there (in terms of N)?

• log₂(N) — since recursive work is halving each level

​

[Step 3] Using (1) and (2), what's a summation representing the total amount of work? Solve for the order of growth.

• total work:

Worksheet Q1: Model Code with Recurrence

Determine the recurrence relation for the method f()

Walkthrough: Understand Code Structure

Base case when the input N <= 1

Walkthrough: Understand Code Structure

Recursive case when N > 1

Walkthrough: Understand Code Structure

Non-recursive work

Walkthrough: Understand Code Structure

Recursive work

Walkthrough: Understand Code Structure

Recursive work

Base case when the input N <= 1

Non-recursive work

T(N) =

Base case

Recursive work + Non-recursive work

Recurrence:

Walkthrough: Code to Recurrence

Worksheet Q2:

Consider the following method:

​

​

​

​

​

​

​

​

​

Worksheet Q2:

For the given triple() method,

​

Code to Recurrence:

• What is the recurrence relation for this method?

Draw a Recurrence Diagram:

• How many branches will each subtree have?
• What is the recursive and non-recursive work for the second level?

Recurrence Relations (solution)

Gradescope: Deques

AND ON YOUR WORKSHEET!

Closing Announcements

• Thanks for coming to section! See you tomorrow in class! Stay safe and stay hydrated :)

​

Please don't hesitate to reach out if you have any

questions or concerns about the course, or if there's

anything else we can help you with! We're here to support

you however we can!