CSE 373 26AU Section 3
Recurrence
Agenda
Announcements
Mon (10/12) | Tues (10/13) | Wed (10/14) | Thurs (10/15) | Fri (10/16) | Sat (10/17) |
| P0 (Review) due @ 22:00 (10:00 PM) |
| | | HW1 (Asymptotic Analysis I) due @ 22:00 (10:00 PM) |
Mon (10/19) | Tues (10/20) | Wed (10/21) | Thurs (10/22) | Fri (10/23) | |
| P1 (Deques) due @ 22:00 (10:00 PM) | | | | |
Extra Practice: Iterative Code Modeling
Some tips
Problem 1a
public static void sunny(int n) {
int count = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j < n * n; j += n) {
count++;
}
for (int k = 1; k < n * n * n; k = 2 * k) {
count++;
}
}
}
n - 1
Problem 1a
public static void sunny(int n) {
int count = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j < n * n; j += n) {
count++;
}
for (int k = 1; k < n * n * n; k = 2 * k) {
count++;
}
}
}
n - 1
n
Because we jump by n until n^2
Problem 1a
public static void sunny(int n) {
int count = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j < n * n; j += n) {
count++;
}
for (int k = 1; k < n * n * n; k = 2 * k) {
count++;
}
}
}
n - 1
n
k takes: 1, 2, 4, 8, . . ., so after m iterations k = 2^m
The loop stops when 2^m = n^3
Solving for m:
Problem 1a
public static void sunny(int n) {
int count = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j < n * n; j += n) {
count++;
}
for (int k = 1; k < n * n * n; k = 2 * k) {
count++;
}
}
}
n - 1
n
MicroTeach: O, Omega, Theta
The Three Bounds
A Picture!
O(n log n)
Θ(n)
Θ(log n), Θ(1)
Θ(n^2)
Θ(2^n)
Θ(n!)
Ω(n log n)
Θ(n)
Θ(log n), Θ(1)
Θ(n^2)
Θ(2^n)
Θ(n!)
O(n log n)
Ω(n log n)
Asymptotically “Less than or equal to”
Asymptotically “Greater than or equal to”
How to get Θ?
f must be both O(g) and Ω(g) to be Θ(g)!�
Think of this as “squeezing” the function from above and below.
Problems 2c, 2d, 2e: True or false?
2c
If a function is in Ω(n), then it could also be in O(n²)
True: It’s possible for a function to both live “below” n2 but “above” n.�Example: n1.5
2d
If a function is in Θ(n), then it could also be in O(n²)
True: Any function that lives “on” the n line must also live “below” n2.
2e
If a function is in Ω(n), then it is always in O(n)
False: An Ω(n) function such as n2 might live in the orange, but it can never be considered O(n).
Case Analysis
What is a case?
A case is when there are different branches (if statements), not dependent on n, that happen as n approaches infinity.
You can analyze the runtime of cases separately from each other!
Runtime Analysis Summary
Given an algorithm, we want to:
In this course, we combine case analysis with asymptotic analysis!
To translate order of growth into mathematical notation, we have our 3 main bounds:
Problem 4
boolean findMatch(int[] values, int target) {
if (values.length == 0) {
return false;
}
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < 5; j++) {
if (values[i] == target) {
return true;
}
}
}
return false;
}
A student claims: "findMatch() is always (n) because it contains a loop over the entire array."
Do you agree or disagree? Explain why
Problem 4
boolean findMatch(int[] values, int target) {
if (values.length == 0) {
return false;
}
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < 5; j++) {
if (values[i] == target) {
return true;
}
}
}
return false;
}
What is the best case runtime of this following code? What is the case in which it happens
Problem 4
boolean findMatch(int[] values, int target) {
if (values.length == 0) {
return false;
}
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < 5; j++) {
if (values[i] == target) {
return true;
}
}
}
return false;
}
What is the best case runtime of this following code? What is the case in which it happens
When values.length == 0?
Asymptotic Analysis: We need n → ∞
Problem 4
boolean findMatch(int[] values, int target) {
if (values.length == 0) {
return false;
}
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < 5; j++) {
if (values[i] == target) {
return true;
}
}
}
return false;
}
What is the best case runtime of this following code? What is the case in which it happens
Best case: Θ(1)
when values[0] == target
Recurrence Analysis Review
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 of a function recursively.��
Base Case
Recursive Case
What is a Recurrence?
An expression that lets us express the runtime of a function recursively.��
Base Case
Recursive Case
Recursive Call
Code To Recurrence
Do Problem 4a!
Hint 1: This is helpful for 4a
4A: Finding Bounds
Outer loop runs N times
N
4A: Finding Bounds
The inner loop depends on the outer loop
N
4A: Finding Bounds
Inside the inner loop, we have a constant time operation
N
4A: 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
4A: Finding Bounds
POSSIBLE RUNTIME:
T(N) = N(N-1)/2 = ½ N2 - ½ N
WORST CASE RUNTIME:
Θ(N2)
N2/2 - N/2 => N2
Best/worst cases agree!
4: Code To Recurrence
4: Code To Recurrence
Base case when the input N <= 1
4: Code To Recurrence
Hint: we did this in 4a
4: Code To Recurrence
It’s N(N-1)/2!
4: Code To Recurrence
Call f(N/2)
Constant addition
Call f(N/2)
Call f(N/2)
Call f(N/2)
4: Code To Recurrence
Calling 4 functions and the input is divided by half each level
Work happening in both outer and inner loops
See 4a
4: Code To Recurrence
Calling 4 functions and the input is divided by half each level
Work happening in both outer and inner loops
See 4a
Can also simplify non-recursive term (and only this term) using Big-O rules.
So you could also have put N2 here.
Master Theorem
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.
There will be some cases where your code does not match this form. It is still possible to find its time complexity, but we will not cover it in this course.
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 N2 here.
Use Master Theorem to find closed form
Original recurrence:
Step 2: Calculate logb(a) and compare it to c
a = 4
b = 2
e = 1
c = 2
logb(a) = log2(4)
log2(4) = 2
c = 2 so logb(a) = c
logb(a) = c so T(n) ∈ Θ(n2log n)
Ta-da!
Closing Announcements
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!