4 of 37

Project 1: Part 5 (Optional)

Posted on Ed. Completely optional!

Extra credit available:

Up to 50 points on project 1 (can’t get over 100%)
Up to 12.5 points on midterm 1 (can’t get over 100%)

DUE before the end of October (show Jake at office hours)

5 of 37

UPDATED DUE DATE: Project 2: Part 1

Build a simple search engine using 1D lists :)

UPDATED DUE DATE: Friday October 14th, 11:59pm

6 of 37

Style Guide

Available here

Linked at the top of the class website :)

7 of 37

Reminder: FALL BREAK!

No class next Monday or Tuesday!

9 of 37

Lower-Order Terms

Name	Function	Examples
constant	1	1, 5, 10
logarithmic	log(n)	log(2n), 3log(n)
linear	n	4n, 0.5n, n
log-linear	n log(n)	3nlog(n), nlog(0.5n)
polynomial	n^c	2n², 5n³
exponential	cⁿ	2ⁿ, 5^{n + 1}

Lower “order”

Higher “order”

More efficient

Less efficient

11 of 37

Simplification Examples

Drop lower order terms and multiplicative factors

Focus on dominant term: term that will increase the fastest

9999+ 0.1 * n

10n¹⁰⁰ + 2ⁿ

log(n) + 10 * n * log(n) + 500n

10¹⁰⁰⁰

0.1nO(n)

2ⁿO(2ⁿ)

10n log n O(n log n)

10¹⁰⁰⁰* 1 O(1)

So here are some examples. If we’re counting operations and we come up with an expression that has n squared plus 2n plus 2 operations, that expression is order n squared. The 2 and the 2n don't matter. Let’s think about what happens if we made n really big. n squared is much more dominant than the other terms. We say that's order n squared.

Even this expression we say is order n squared. So in this case, for lower values of n, this term is going to be the big one in terms of number of steps. I have no idea how I wrote such an inefficient algorithm that it took 100 steps to do something. But if we had that expression for smaller values of n, this matters a lot. This is a really big number. But when we’re interested in the growth, then that's the term that dominates. When we have expressions, if it's a polynomial expression, it's the highest order term. It's the term that captures the complexity. Both of these are quadratic. This term is order n, because n grows faster than log of n.

This funky looking term, even though that looks like the big number there and it is a big number, that expression we see is order n log n. Because again, if I plot out as how this changes as I make n really large, this term eventually takes over as the dominant term. What about that one? What's the big term there?

12 of 37

Example: create_countdown

def create_countdown(x):

result = []

for i in range(x):

result.insert(0, i)

return result

O(n)

O(1)

n * n + 1

= n^2 + 1

=> O(n^2)

O(n)

13 of 37

Example: create_countdown

def create_countdown(x):

result = []

for i in range(x-1, -1, -1):

result.append(i)

return result

O(n)

O(1)

n * 1 + 1

= n + 1

=> O(n)

O(1)

14 of 37

Space Complexity

15 of 37

Space Complexity

The same way we’ve been thinking about time complexity, we can analyze the space complexity of a particular solution.

Space Complexity refers to how much space in memory a program uses when it runs (including storing the parameter)

For time complexity, our unit was “operations”. For space complexity, we think about number of single “units” written to memory:

Integers
Booleans
Characters
etc.

16 of 37

Space Complexity - Big O

We talk about space complexity in terms of Big O as well.

def mystery(n): num1 = n * 2 num2 = n + 6 return num1 + num2

Stores parameter n

Creates 2 new integers in memory

O(3) = O(1), so constant space complexity

17 of 37

Space Complexity - Big O

We talk about space complexity in terms of Big O as well.

def mystery1(nums, item): length = len(nums) new_list = [] for num in nums: if num == item: break new_list.append(num) return new_list

In the worst case, creates a new list with n items in it (where n is the length of the given list `nums`), and 1 new integer variable in memory.

O(n + 1) = O(n), linear space complexity

18 of 37

Space Complexity - Big O

We talk about space complexity in terms of Big O as well.

def mystery2(nums): length = len(nums) new_list = [] for i in range(length): new_list.append([]) for j in range(length): new_list[i].append(nums[i] * nums[j]) return new_list

Creates a new list with n lists inside of it. Each of those n lists contain n items (where n is the length of the given list `nums`)

O(n * n + n) = O(n^2), polynomial space complexity

19 of 37

Big O Practice

20 of 37

Example: remove_vowel_start

def remove_vowel_start(items, item):

if item in items and item[0] in 'aeiou':

items.remove(item)

return True

return False

O(n)

O(1)

Time Complexity:

O(n) + O(1) + O(n)

= O(n + 1 + n)

= O(2n + 1)

= O(n)

O(n)

Space complexity:

Input list of size n

No new variables

O(n)

21 of 37

Example: clean_list_v1

def clean_list_v1(my_list):

for num in my_list:

if 0 in my_list:

my_list.remove(0)

O(n)

Time Complexity:

O(n) * (O(n) + O(n))

= O(n * 2n)

= O(2n^2)

= O(n^2)

O(n)

Space complexity:

No new variables!

O(n)

22 of 37

Example: clean_list_v2

def clean_list_v2(my_list):

while 0 in my_list:

my_list.remove(0)

O(n)

Time Complexity:

O(n) * O(n)

= O(n^2)

O(n)

Space complexity:

No new variables!

O(n)

23 of 37

Example: clean_list_v3

def clean_list_v3(my_list):

result = []

for num in my_list:

if num != 0:

result.append(num)

return result

O(n)

Time Complexity:

O(1) + O(n) * O(1)

= O(n)

Space complexity:

Created a new list up to

size n.

O(n) + O(n)

= O(2n)

= O(n)

O(1)

24 of 37

Example: repeat_letters

def repeat_letters(my_string):

for char in my_string:

for i in range(5):

print(char)

O(n)

O(1)

Time Complexity:

O(n) * (O(1) + O(1))

= O(n) * O(1)

= O(n)

O(1)

Space complexity:

No new variables!

O(n)

25 of 37

Example: rotate_colors

def rotate_colors(pixels):

pixels_copy = copy.deepcopy(pixels)

for row in len(pixels):

for col in len(pixels[row]):

for value in len(pixels[row][col]):

pixels_copy[row][col][value] = pixels[row][col][value + 1 % 3]

return pixels_copy

O(n)

O(1)

Time Complexity:

(where k is # of columns)

O(n*k) + O(n) * O(k) * O(1)

= O(n*k) + O(n*k)

= O(n*k)

O(k)

Space complexity:

Created a copy of the 2D list

O(n^2) + O(n^2)

= O(2n^2)

= O(n^2)

O(n*k)

O(1)

26 of 37

Example: binary_search

def binary_search(nums, target):

low = 0

high = len(nums) - 1

middle = 0

while low <= high:

mid = (high + low) // 2

if nums[mid] < target:

low = mid + 1

elif nums[mid] > target:

high = mid - 1

else:

return mid

return -1

O(1)

O(?)

27 of 37

Example: binary_search

5	10	12	13	28	45	67	80	82	85	87	87	92	98	99

binary_search(my_list, 12)

28 of 37

Example: binary_search

5	10	12	13	28	45	67	80	82	85	87	87	92	98	99

low = 0

high = 14

middle = 0

binary_search(my_list, 12)

29 of 37

Example: binary_search

5	10	12	13	28	45	67	80	82	85	87	87	92	98	99

low = 0

high = 14

middle = 7

binary_search(my_list, 12)

30 of 37

Example: binary_search

5	10	12	13	28	45	67	80	82	85	87	87	92	98	99

low = 0

high = 6

middle = 7

binary_search(my_list, 12)

31 of 37

Example: binary_search

5	10	12	13	28	45	67	80	82	85	87	87	92	98	99

low = 0

high = 6

middle = 3

binary_search(my_list, 12)

32 of 37

Example: binary_search

5	10	12	13	28	45	67	80	82	85	87	87	92	98	99

low = 0

high = 2

middle = 3

binary_search(my_list, 12)

33 of 37

Example: binary_search

5	10	12	13	28	45	67	80	82	85	87	87	92	98	99

low = 0

high = 2

middle = 1

binary_search(my_list, 12)

34 of 37

Example: binary_search

5	10	12	13	28	45	67	80	82	85	87	87	92	98	99

low = 2

high = 2

middle = 1

binary_search(my_list, 12)

35 of 37

Example: binary_search

5	10	12	13	28	45	67	80	82	85	87	87	92	98	99

low = 2

high = 2

middle = 2

binary_search(my_list, 12)

36 of 37

Example: binary_search

def binary_search(nums, target):

low = 0

high = len(nums) - 1

middle = 0

while low <= high:

mid = (high + low) // 2

if nums[mid] < target:

low = mid + 1

elif nums[mid] > target:

high = mid - 1

else:

return mid

return -1

O(1)

# of times I need to divide my list in half until I have just one element

Ex: 128 // 2 // 2 // 2 // 2 // 2 // 2 // 2� -> 7

2 ^ 7 = 128

2 ^ x = n

x = log(n)

O(log(n))

1 of 37

2 of 37

3 of 37

4 of 37

5 of 37

6 of 37

7 of 37

8 of 37

9 of 37

10 of 37

11 of 37

12 of 37

13 of 37

14 of 37

15 of 37

16 of 37

17 of 37

18 of 37

19 of 37

20 of 37

21 of 37

22 of 37

23 of 37

24 of 37

25 of 37

26 of 37

27 of 37

28 of 37

29 of 37

30 of 37

31 of 37

32 of 37

33 of 37

34 of 37

35 of 37

36 of 37

37 of 37