1 of 14

CSE 163

Introduction to Efficiency�

Suh Young Choi�

🎶 Listening to: Good Omens soundtrack

💬 Before Class: Most anticipated media release of the year? (Has it already happened?)

2 of 14

Announcements

Y’all did it! HW4 and LR4 are due tonight!

  • Previously had been a miscalculation
  • Make sure you are double-checking!

​

THA5, LR5, and CP5 releasing after class today

  • Will spend some time at the end to preview the assessment
  • Last THA and LR of the quarter!

​

Reminders

  • Bonus dataset finding activity due by next Monday
  • THA2/LR2 final submissions by next Tuesday

​

2

3 of 14

This Time

  • Efficiency
  • Runtime analysis
  • Big-O

Last Time

  • Dissolve
  • How to join datasets

3

4 of 14

Method 1: Timing

In the reading, we looked at how to calculate the time it takes to run

  • This can be tricky to get right since many factors affect time it takes to run program

​

�Can still get a general idea of �how two algorithms “scale”�by looking at time it takes �to run.

​

​

​

​

​

​

​

​

4

5 of 14

Method 2: Count steps

Assumption: A single “simple” line of code takes the same amount of time to run in Python.

Examples:

num = 5 + 10;

print(“hello);

x > 5 and x % 2 == 0

​

​

5

num = 5 + 10

print(“hello”)

num > 5 and num % 2 == 0

​

​

  • Blocks of code
    • Sum of all the lines
  • For loops
    • Number of steps in body multiplied by number of times loop runs
  • Function call
    • The number of steps in its body

6 of 14

Counting example

6

def mystery(n: int) -> int:

x = n + 10

while n < 5:

x *= 2

n += 1

return x

​

mystery(1)

​

mystery(4)

​

7 of 14

Counting example

7

def mystery(n: int) -> int:

x = n + 10 # + 1

while n < 5: # + (5-n) * 2

x *= 2

n += 1

return x # + 1

​

mystery(1) # 10 steps

​

mystery(4) # 4 steps

​

8 of 14

Growth rate

We often think of algorithms in terms of growth rate in terms of the input or input data size (n)

​

Think of the runtime of: 5n3 + 4n2 + 3n + 7.

​

All terms seem significant when we look at smaller inputs.

​

However, what happens when n becomes extremely large? At that point the term with the largest power of n will dominate (n3).

​

We say it runs on the order of n3 or O(n3) (Big Oh of n cubed).

8

9 of 14

Quadratic

Comparison

9

10 of 14

Complexity classes

A category of algorithm efficiency based on the algorithm's relationship to the input size n

10

Class

Constant

If n doubles, then

Constant

O(1)

unchanged

Linear

O(n)

doubles

Quadratic

O(n2)

quadruples

Cubic

O(n3)

Multiplies by 8

...

​

​

Exponential

O(2n)

Multiplies drastically

11 of 14

LR may include…

11

  • Two methods for measuring efficiency
  • Counting steps (and how)
  • Big-O

12 of 14

HW5 tips

12

Summary

  • Using geopandas and matplotlib to create maps reflecting food desert data
  • Accompanied with a 4-question writeup (similar to HW3; see Lesson 11 for tips on approaching this)

​

Resources you may find helpful

  • Lessons 15-16
  • Section 5: Geospatial Data

​

Caveats

  • Filter down to necessary columns before expensive calculations like dissolve
  • Check the contents of your columns and what they represent!

​

​

13 of 14

Project Part 1 Out (Sort of)

Project has a few parts

  • Proposal (due Monday 8/7)
  • Code and Report
  • Presentation Video
  • Peer Feedback

​

Spec out now to give you time to start thinking about it or working on it, but the actual assignment won’t open till next Tuesday

  • Spec is long to provide context for whole project
  • Make sure you can access Gradescope!

​

Recommended that you work in groups (up to 3 people per group).

13

14 of 14

Before Next Time

  • Complete Lesson 18
    • Remember not for points, but do go towards Checkpoint Tokens
  • HW4 / LR4 due tonight!
  • HW5 / LR5 / CP5 releasing after class!
  • Bonus dataset finding activity due Monday
  • Proposals release on Tuesday

​

Next Time

  • Intro to numpy
  • Image manipulation

​

14