Lecture 5: Case Analysis

CSE 373: Data Structures and Algorithms

1

Please log onto Live Lecture Ed Thread to submit live lecture questions

Research Study with Leah

• Belonging and CS TAs Research Study
• Leah Perlmutter (she/her)
• leahperl@uw.edu
• tinyurl.com/belonging-study

CSE 373 22 SP – CHAMPION

2

Announcements

• Exercise 1 Released
• - Individual assignment
• - Due Friday JULY 8TH
• ​
• Proj 1 Due Wednesday July 6th
• Partner Project! (Groups of up to 3 people)
• Find Partners on Project Partner Megathread on Ed
• Change partners on Gradescope

CSE 373 22 SP – CHAMPION

3

P1 Deques

CSE 373 SP 18 - KASEY CHAMPION

4

P1: Deques

• Deque ADT: a double-ended queue
• Add/remove from both ends, get in middle

​

• This project builds on ADTs vs. Data Structure Implementations, Queues, and a little bit of Asymptotic Analysis
• Practice the techniques and analysis covered in LEC 02 & LEC 03!

​

• 3 components:
• Debug ArrayDeque implementation
• Implement LinkedDeque
• Run experiments

ArrayDeque

LinkedDeque

P1: Sentinel Nodes

• Reduce code complexity & bugs
• Tradeoff: a tiny amount of extra storage space for more reliable, easier-to-develop code

Tired of running into these?

Find yourself writing case after case in your linked node code?

Client View:

Implementation:

[3, 9]

Introducing

Sentinel Nodes

P1: Gradescope & Testing

• From this project onward, we’ll have some Gradescope-only tests
• Run & give feedback when you submit, but only give a general name!
• The practice of reasoning about your code and writing your own tests is crucial
• Use Gradescope tests as a double-check that your tests are thorough
• To debug Gradescope failures, your first step should be writing your own test case
• You can submit as many times as you want on Gradescope (we’ll only grade the last active submission)
• If you’re submitting a lot (more than ~6 times/hr) it will ask you to wait a bit
• Intention is not to get in your way: to give server a break, and guess/check is not usually an effective way to learn the concepts in these assignments

1. Write Implementation

2. Think about edge cases, Write your own tests

3. Run your own tests

4. Run Gradescope tests as a double-check

P1: Working with a Partner

• P1 Instructions talk about collaborating with your partner
• Adding each other to your GitLab repos
• Recommendations for partner work:
• Pair programming! Talk through and write the code together
• Two heads are better than one, especially when spotting edge cases ☺
• Meet in real-time! Consider screen-sharing via Zoom
• Be kind! Collaborating in our online quarter can be especially difficult, so please be patient and understanding – partner projects are usually an awesome experience if we’re all respectful
• We expect you to understand the full projects, not just half
• Please don’t just split the projects in half and only do part
• Please don’t come to OH and say “my partner wrote this code, I don’t understand it, can you help me debug it?”

Questions?

CSE 373 SP 18 - KASEY CHAMPION

9

Big O

CSE 373 19 SU - ROBBIE WEBER

Definition: Big-O

CSE 332 SU 18 - ROBBIE WEBER

11

Note: Big-O definition is just an upper-bound, not always an exact bound

CSE 332 SU 18 - ROBBIE WEBER

12

Big-O is just an upper bound thay may lose and may not describe the function fully. For example the following is true:

This is a big idea!

Note: Big-O definition is just an upper-bound, not always an exact bound (plots)

• What do we want to look for on a plot to determine if one function is in the big-O of the other?

You can sanity check that your g(n) function (the dominating one) overtakes or is equal to your f(n) function after some point and continues that greater-than-or-equal-to trend towards infinity

CSE 373 SP 18 - KASEY CHAMPION

13

n³

n⁵

n⁴

10n² + 15n

The visual representation of big-O and asymptotic analysis is a big idea!

Tight Big-O Definition Plots

CSE 373 SP 18 - KASEY CHAMPION

14

n²

10n² + 15n

Uncharted Waters: a different type of code model

CSE 373 SP 22 - CHAMPION

15

Find a model f(n) for the running time of this code on input n. What’s the Big-O?

​

boolean isPrime(int n){

int toTest = 2;

while(toTest < n){

if(n % toTest == 0) {

return false;

} else {

toTest++;

}

}

return true;

}

​

CSE 332 SU 18 - ROBBIE WEBER

16

Note: this right graph’s tight O bound is O(n) and its tight Omega bound is Omega(n). This is what most of the functions we’ll deal with will look like, but there exists some code that would produce runtime functions like on the left.

f(n) = n

prime runtime function

​

O, and Omega, and Theta [oh my?]

Big Theta is “equal to”

• My code takes “exactly”* this long to run
• *Except for constant factors and lower order terms

CSE 332 SU 18 - ROBBIE WEBER

17

f(n) = n

To define a big-Theta, you expect the tight big-Oh and tight big-Omega bounds to be touching on the graph (meaning they’re the same complexity class)

O, and Omega, and Theta [oh my?]

• Big-O is an upper bound
• My code takes at most this long to run

​

• Big-Omega is a lower bound
• My code takes at least this long to run

​

​

• Big Theta is “equal to”
• My code takes “exactly”* this long to run
• *Except for constant factors and lower order terms

CSE 332 SU 18 - ROBBIE WEBER

18

Examples

• 4n² ∈ Ω(1)
• true
• 4n² ∈ Ω(n)
• true
• 4n² ∈ Ω(n²)
• true
• 4n² ∈ Ω(n³)
• false
• 4n² ∈ Ω(n⁴)
• false

CSE 332 SU 18 - ROBBIE WEBER

19

• 4n² ∈ O(1)
• false
• 4n² ∈ O(n)
• false
• 4n² ∈ O(n²)
• true
• 4n² ∈ O(n³)
• true
• 4n² ∈ O(n⁴)
• true

Questions

CSE 373 20 SP – CHAMPION & CHUN

20

Our Upgraded Tool: Asymptotic Analysis

CSE 373 SP 22 - CHAMPION

Asymptotic

Analysis

2

O(n²)

Θ(n²)

f(n) = 10n² + 13n + 2

We’ve upgraded our Asymptotic Analysis tool to convey more useful information! Having 3 different types of bounds means we can still characterize the function in simple terms, but describe it more thoroughly than just Big-Oh.

Our Upgraded Tool: Asymptotic Analysis

CSE 373 SP 22 - CHAMPION

Asymptotic

Analysis

2

O(n)

Does not exist for this function

isPrime()

Big-Theta doesn’t always exist for every function! But the information that Big-Theta doesn’t exist can itself be a useful characterization of the function.

Algorithmic Analysis Roadmap

CSE 373 SP 22 - CHAMPION

CODE

Code Modeling

RUNTIME

FUNCTION

1

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

a[i] = 1;

b[i] = 2;

}

f(n) = 2n

Asymptotic

Analysis

2

O(n)

Θ(n)

We just finished building this tool to characterize a function in terms of some useful bounds!

Now, let’s look at this tool in more depth. How exactly are we coming up with that function?

Case Analysis

CSE 373 SP 18 - KASEY CHAMPION

24

Case Study: Linear Search

CSE 373 SP 22 - CHAMPION

arr

toFind

2

toFind

8

arr

Best Case

Worst Case

On Lucky Earth

On Unlucky Earth (where it’s 2020 every year)

arr

toFind

2

i

arr

toFind

8

f(n) = 3n + 1

f(n) = 2

O(1)

Θ(1)

O(n)

Θ(n)

After asymptotic analysis:

After asymptotic analysis:

Case Analysis

• Case: a description of inputs/state for an algorithm that is specific enough to build a code model (runtime function) whose only parameter is the input size
• Case Analysis is our tool for reasoning about all variation other than n!
• Occurs during the code 🡪 function step instead of function 🡪 O/Ω/Θ step!

​

CSE 373 SP 22 - CHAMPION

• (Best Case: fastest/Worst Case: slowest) that our code could finish on input of size n.
• Importantly, any position of toFind in arr could be its own case!
• For this simple example, probably don’t care (they all still have bound O(n))
• But intermediate cases will be important later

• Caution

CSE 373 19 SU - ROBBIE WEBER

CSE 373 19 SU - ROBBIE WEBER

“worst input”: input that causes the code to run slowest.

Other cases

CSE 373 19 SU - ROBBIE WEBER

How to do case analysis

• 1. Look at the code, understand how thing could change depending on the input.
• How can you exit loops early?
• Can you return (exit the method) early?
• Are some if/else branches much slower than others?
• 2. Figure out what inputs can cause you to hit the (best/worst) parts of the code.
• 3. Now do the analysis like normal!

CSE 373 19 SU - ROBBIE WEBER

Algorithmic Analysis Roadmap

CODE

BEST CASE

FUNCTION

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

if (arr[i] == toFind) {

return i;

}

}

return -1;

f(n) = 2

2

O(n)

Θ(n)

1

Asymptotic

Analysis

WORST CASE

FUNCTION

OTHER CASE

FUNCTION

Case Analysis

f(n) = 3n+1

Review Algorithmic Analysis Roadmap

CODE

BEST CASE

FUNCTION

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

if (arr[i] == toFind) {

return i;

}

}

return -1;

f(n) = 2

2

O(1)

Θ(1)

1

Asymptotic

Analysis

WORST CASE

FUNCTION

OTHER CASE

FUNCTION

Case Analysis

f(n) = 3n+1

When to do Case Analysis?

• Imagine a 3-dimensional plot
• Which case we’re considering is one dimension
• Choosing a case lets us take a “slice” of the other dimensions: n and f(n)
• We do asymptotic analysis on each slice in step 2

f(n)

n

toFind position

At front

(Best Case)

Not present

(Worst Case)

Questions

CSE 373 20 SP – CHAMPION & CHUN

35