Lecture 5: Big O and

Case Analysis

CSE 373: Data Structures and Algorithms

Answer the Warm Up:

PollEv.com/champk

​

​

​

​

​

1

CSE 373 24WI

CSE 373 24WI

1

Warm Up

Which of the following statements are TRUE?

​

Select all options that apply:

• A Big-Θ bound will exist for every function
• If a runtime function is O(n²) it can’t also be Ω(n²)
• A piece of code whose runtime function is f(n) = 3n + 6 is in the Big-O of O(n²)
• If a runtime function is in Θ(n) then it could be in O(logn)

CSE 373 24WI

2

Announcements

• Project 0 – 143 Review turn in closes Sunday Jan 14th
• Project 1 - Deques released yesterday
• Due Thursday Jan 18^th
• Exercise 1 out - Due Tuesday Jan 16th

CSE 373 24WI

3

P1 Deques

CSE 373 24WI

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!

​

• 2 components:
• Debug ArrayDeque implementation
• Implement LinkedDeque

ArrayDeque<E>

DEQUEUE ADT

State

Collection of ordered items

Count of items

Behavior

addFirst(item) add to front

addLast(item) add to end

removeFirst() remove from front

removeLast() remove from end

size() count of items

isEmpty() count is 0?

get(index) get 0-indexed element

LinkedDeque<E>

CSE 373 24WI

5

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

CSE 373 24WI

6

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

CSE 373 24WI

7

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?”

How to Pair Program (Helpful YouTube)

How to Pair Program (Chaos Mode)

CSE 373 24WI

8

Questions?

CSE 373 24WI

9

Big O Proofs

CSE 373 24WI

10

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 373 24WI

11

Examples

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

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

CSE 373 24WI

12

Comparing Complexity Classes

https://www.bigocheatsheet.com/

CSE 373 24WI

13

Big-O is an upper-bound, not a fit

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

If we want the most-informative upper bound, we’ll ask you for a simplified, tight big-O bound.

O(n^2 ) is the tight bound for the function f(n) = 10n2+15n. See the graph below – the tight big-O bound is the smallest upper bound within the definition of big-O.

If you zoom out a bunch, the your tight bound and your function will be overlapping compared to other complexity classes.

CSE 373 24WI

14

Big-Omega definition Plots

2n³

n²

n

1

n³

CSE 373 24WI

15

Simplified, tight big-O

In this course, we’ll essentially use:

• Polynomials eg: n^c where c is a constant: eg n, n³, sqrt(n), 1
• Logarithms eg: logn
• Exponents eg: cⁿ where c is a constant: eg 2ⁿ, 3ⁿ
• Combinations of theses eg: log(log(n)), nlogn, (log(n)²

​

For this course:

• a “tight big-O” is the slowest growing upper bound
• a “tight big-Ω” is the fastest growing lower bound
• A Θ is always “tight” by definition as it is a fit
• A “simplified” big-O, big-Ω or big-Θ
• does not have any non-dominant terms
• does not have any coefficients
• does not have any constants factors

CSE 373 24WI

16

Questions?

CSE 373 24WI

17

Where are we?

• Now we can use complexity classes to understand the range of runtime growth rate as size of data scales upward

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

a[i] = 1;

b[i] = 2;

}

O(n)

f(n) = 2n

COMPLEXITY

CLASS

Code Modeling

RUNTIME

FUNCTION

Asymptotic Analysis

1

2

CSE 373 24WI

18

Our Upgraded Tool: Asymptotic Analysis

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.

Ω(n²)

CSE 373 24WI

19

Our Upgraded Tool: Asymptotic Analysis

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.

Ω(1)

CSE 373 24WI

20

Algorithmic Analysis Roadmap

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?

Ω(n)

CSE 373 24WI

21

Case Analysis

CSE 373 24WI

22

Case Study: Linear Search

int linearSearch(int[] arr, int toFind) {

for (int i = 0; i < arr.length; i++) {

if (arr[i] == toFind)

return i;

}

return -1;

}

arr

toFind

2

toFind

8

arr

The number of operations doesn’t only depend on n.

Even once the since of the data is fixed there are different behaviors based on the organization of the data.

• If toFind is in arr[0] we only need one iteration
• f(n) = 4 → O(1)
• If toFind is not in arr, we’ll need n iterations
• f(n) = 3n + 1 → O(n)

CSE 373 24WI

23

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:

CSE 373 24WI

24

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!

• Best Case = fastest that our code could finish on input of size n
• 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

CSE 373 24WI

25

Caution: Common Misunderstanding

Best/Worst case is based on all variation other than value of n

Incorrect - based on specific values of n

• “The best case is when n=1, worst is when n=infinity”
• “The best case is when front is null”
• “The best case is when overallRoot is null”
• “The best case is when n is an even number”

Correct - based on state of data structure regardless of n

• “The best case is when the node I’m looking for is at front, the worst is when it’s not in the list”
• “Insertion Sort’s best case is when the collection is already sorted, its worst case is when its reverse sorted”
• “For a method that removes duplicates from a List, the best case is when there are no duplicates and the worst case is when the whole List is duplicates”
• “The best case is when the BST is perfectly balanced, the worst is when it’s a single line of nodes”

CSE 373 24WI

26

Other cases

“Assume X won’t happen” case

• Assuming our array won’t need to resize is the most common example

​

“Average” case

• Assuming your input is random
• Need to specify what the possible inputs are and how likely they are
• f(n) is now the average number of steps on a random input of size n

​

“In-practice” case

• This isn’t a real term (I just made it up)
• Making some reasonable assumptions about how the real-world is probably going to work
• We’ll tell you the assumptions and won’t ask you to come up with these assumptions on your own
• Then do worst-case analysis under those assumptions

​

All of these can be combined with any of O, Ω, and θ

CSE 373 24WI

27

How to do case analysis

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

CSE 373 24WI

28

Algorithmic Analysis Roadmap

2

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

if (arr[i] == toFind) {

return i;

}

}

return -1;

f(n) = 2

O(n)

Θ(n)

f(n) = 3n+1

Ω(n)

1

CSE 373 24WI

29

Review Algorithmic Analysis Roadmap

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

if (arr[i] == toFind) {

return i;

}

}

return -1;

2

1

f(n) = 2

f(n) = 3n+1

O(1)

Θ(1)

Ω(1)

CSE 373 24WI

30

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)

CSE 373 24WI

31

Appendix

CSE 373 24WI

32

Applying Big O Definition

Show that

is

Apply definition term by term

Add up all your truths

CSE 373 24WI

33

Exercise: Proving Big O

CSE 373 24WI

34

Writing Big-O Proofs

CSE 373 24WI

35

Big-O as an upper bound

Big-O is just an upper bound. It doesn’t have to be a good upper bound

​

If we want the best upper bound, we’ll ask you for a simplified, tight big-O bound. O(n²) is the tight bound for this example.

​

It is (almost always) technically correct to say your code runs in time O(n!).

DO NOT TRY TO PULL THIS TRICK IN AN INTERVIEW (or exam)!

CSE 373 24WI

36

Big-O is an upper-bound, not a fit

CSE 373 24WI

37