CSE 163
Introduction to Efficiency�
Suh Young Choi�
🎶 Listening to: David Garrett
💬 Before Class: Most anticipated media release of the year? (Has it already happened?)
Announcements
Y’all did it! HW4 is due tonight!
THA5 and LR5 releasing after class today
Reminders
2
Education Recap
Common plot mishaps:
Common conceptual mishaps:
3
This Time
Last Time
4
Method 1: Timing
In the reading, we looked at how to calculate the time it takes to run
�Can still get a general idea of �how two algorithms “scale”�by looking at time it takes �to run.
5
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
6
num = 5 + 10
print(“hello”)
num > 5 and num % 2 == 0
Counting example
7
def mystery(n: int) -> int:
x = n + 10
while n < 5:
x *= 2
n += 1
return x
mystery(1)
mystery(4)
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
Quadratic
Comparison
9
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 |
Group Work:
Best Practices
When you first working with this group:
Tips:
11
Before Next Time
Next Time
12