1 of 59

AddisCoder: Week 2

Lecture 10B:

Time Complexity

2 of 59

Algorithms

3 of 59

Algorithms

An algorithm is the process that you use to get to an answer. It is the series of steps that you execute to to solve a problem.

For each of these paths, the rule that you decide where to turn is your algorithm. The path itself is the solution that your algorithm comes up with.

Algorithm 3

At each intersection, take a turn if that puts me closer to the White House.

Algorithm 4

At each intersection, make a random turn. Walk until you reach the White House.

4 of 59

Algorithms

Examples of other algorithms

5 of 59

Algorithms

Examples of other algorithms

How to make change as a shopkeeper

6 of 59

Algorithms

Examples of other algorithms

How to make change as a shopkeeper

�Algorithm 1:

For the change amount, give the largest coin that is less than the remaining change amount, and subtract from remaining change to give.
Repeat step 1 over and over (until remaining change to give is $0.00)

7 of 59

Algorithms

Examples of other algorithms

How to make change as a shopkeeper

Algorithm 2:

Given them change amount ($X.XX) * 100 pennies.

8 of 59

Algorithms

Examples of other algorithms

How to sort a pile of exams into alphabetical order
Sort all papers into 26 piles by the first letter of the name only (A, B, …)
Sort each of the 26 piles into 26 piles by the second letter of the name
Repeat until all piles are of size 1, then combine

9 of 59

Algorithms in Industry

Recommender Systems: a type of algorithm that recommends content to you based on what you’ve already watched (by looking at what other people with similar tastes have watched).

10 of 59

Algorithms in Industry

Trading Algorithms: financial algorithms that look at the historical stock price data and try to predict future pricing (so as to decide when is best to buy)

11 of 59

Tourist Walks

Which of the 4 algorithms produced the best path?

Depends on what you care about!

12 of 59

Complexity

13 of 59

Complexity

Complexity refers to how we measure programming efficiency in an objective way.

We think about this to...

predict how much time needed to solve problem with particular input size
be able to compare and pick a “best” algorithm among multiple algorithms

14 of 59

Evaluating Program Runtime

Two approaches we can take to measure runtime:

Measure with a timer
Count number of operations

Order of growth: simplify counting the number of operations while keeping high-level behavior

15 of 59

Measuring Time

16 of 59

Timing a Program

��Can use time module

Get the time before you call function

Call function

Stop clock

import time def cels_to_fahr(celsius): return celsius * 9 / 5 + 32 t0 = time.time_ns() cels_to_fahr(100000) t1 = time.time_ns() - t0 print('t = ' + str(t1) + ' nanoseconds') print('t = '+ str(round(t1 / 1000000, 2)) + ' milliseconds')

17 of 59

Timekeeping Problems

What if you and your friend travel the same route at different speeds!

Maybe you walk faster
Maybe your friend is on a scooter and you’re walking
Maybe you get tired more easily

Many factors! Same problems with measuring time for an algorithm

What if one computer has a faster processor than the other?
What if one computer has a limit on how much power it can consume?
What if one computer has less memory than the other?

18 of 59

Timing Programs: Inconsistent

Goal: evaluate different algorithms

Running time:

✅ varies between algorithms

❌ varies between implementations

❌ varies between computers

❌ is not predictable based on small inputs

❌ varies for different inputs, cannot express relationship between inputs and time

Our goal here is to evaluate algorithms. Do different algorithms have different amounts of time associated with them? The good news is is that if we measure running time, it will certainly vary as the algorithm changes. Just what we want to measure.

One of the problems is that it will also vary if we change the implementation. For example, if we use a loop and one loop has a few more steps inside of it than another algorithm, the time is going to change. But, we don’t actually really care about that difference.

Next, this time is going to depend on the computer. A newer computer or a computer with better specs will run faster than an older one with less memory or CPU. That’s not going to help us measure how fast an algorithm is.

And even if we could measure the timing on a small-sized inputs, it doesn’t necessarily predict what happens when we pass in huge inputs because it might take more time to get those inputs out of memory and such.

So what this means is that timing will vary based on what we’d like to measure, but it will also depend on a lot of other factors that make this measurement not that valuable.

19 of 59

Counting Operations

20 of 59

Counting Operations

Assume these steps take constant time:

mathematical operations
comparisons
assignments
accessing items in memory

Count number of operations executed as function of input size

def mysum(x):

total = 0

for i in range(x + 1):

total = total + i

return total

total = 0 => 1 op

range => loop x times

every time increment => 1 op

inside for:

total + i => 1 op

store into total => 1 op

return => 1 op

total: 1 + 3x + 1

5 + 32

return value, *, /, + = 4 ops

def mysum(x): total = 0 for i in range(x): total = total + i return total

def c_to_f(c): return c * 9.0/5 + 32

So we can’t objectively measure how fast our code is by seeing how fast our computer runs that code. Let’s take a look at counting operations instead. We’re going to make the following assumption. We’re going to identify a set of operations that the machine do for us automatically and instantaneously. That would be things like arithmetic or mathematical operations, multiplication, division, subtraction, comparisons, something equal to another thing, something greater than, something less than, assignments, set a name to a value, and retrieval from memory. We’re going to assume that all of these operations take about the same amount of time inside our computers.

The good thing here is then it doesn't matter which machine we’re using. We’re measuring how long the algorithm takes by counting how many operations of this type are done inside our code, and we’ll use that count to come up with a number of operations executed as a function of the size of the input.

21 of 59

Counting Operations

total = 0 => 1 op

range => loop x times

every time increment => 1 op

inside for:

total + i => 1 op

store into total => 1 op

return => 1 op

total: 1 + 3x + 1

total = 0 => 1 op

i = 0 => 1 op

while => loop x times

i comparison => 1 op

inside while:

total = total + i => 2 op

i = i + 1 => 2 op

return => 1 op

total: 1 + 1 + 5x + 1

def mysum(x): total = 0 for i in range(x): total = total + i return total

def mysum(x): total = 0 i = 0 while i < x: total = total + i i = i + 1 return total

22 of 59

Counter Operations: Nested Loops

How many times do we print? x² times

def mystery(x): for i in range(x): for j in range(x): print(i, j)

23 of 59

Counting Operations: Better

Goal: evaluate different algorithms

Running time:

✅ varies between algorithms

24 of 59

Different Inputs Changes How Program Runs

element first element in list: best case

element not in list: worst case

look through about half of elements in list: average case

want to measure behavior in a general way

def search_for_element(lst, element): for item in lst: if item == element: return True return False

25 of 59

Best, Average, Worst Cases

Suppose given list lst of some length len(lst)

best case: minimum running time over all possible inputs of given size, len(lst)

constant for search_for_element
ex: first element in any list

average case: average running time over all possible inputs of given size, len(lst)

practical measure

worst case: maximum running time over all possible inputs of given size, len(lst)

linear in length of list for search_for_element
must search entire list and not find it

26 of 59

Counting Operations: Slightly Better

Goal: evaluate different algorithms

Running time:

✅ varies between algorithms

❌ varies between implementations

✅ independent between computers

❌ no clear definition of which operations to count

✅ varies for different inputs, can express relationship between inputs and count

Another good news is the count is independent of what computer we run on. As long as all of our computers come with the same set of basic operations, we don’t care what the time of my computer is vs yours when we’re measuring the number of operations. The number of operations doesn’t change depending on what computer we’re running on.

Earlier, we made an assumption that getting something from memory takes the same amount of time that it takes to do a mathematical operation. That might not actually be accurate, so how do we determine which operations actually take the same time and should be counted as an operation?

And lastly, counting the number of operations does differ depending on what the input is, and we can use this to come up with a relationship between the inputs and the count. And for the most part, it reflects the algorithm and not the exact implementation. But there’s still some problems with this, as we’ve talked about.

27 of 59

Still Need Better Way

Timing and counting evaluate implementations

Timing evaluates machines

Want to:

evaluate algorithm
evaluate scalability
evaluate in terms of input size

To be continued...

28 of 59

Evaluating Program Runtime

Two approaches we can take to measure runtime:

Measure with a timer
Time the program using an accurate stopwatch.
Compare how long 2 different algorithms take to run.
Problems:

Depends on the hardware the code is running on
Varies from run-to-run (based on available memory, etc.)

Count number of operations

Order of growth: simplified counting while keeping high-level behavior

29 of 59

Evaluating Program Runtime

Three approaches we can take to measure runtime:

Measure with a timer
Count number of operations
Assume each “operation” takes 1 unit of time, count number of operations
Count uses variable “n” which is the size of input
Pros: takes into account size of input
Cons: What counts as an “operation”? Unruly answer with many terms?

Order of growth: simplified counting while keeping high-level behavior

total = 0 => 1 op

range => loop x times

every time increment => 1 op

inside for:

total + i => 1 op

store into total => 1 op

return => 1 op

total: 1 + 3x + 1

def mysum(x): total = 0 for i in range(x): total = total + i return total

30 of 59

Evaluating Program Runtime

Two approaches we can take to measure runtime:

Measure with a timer
Count number of operations

Order of growth: Simplified counting while keeping high-level behavior

31 of 59

Big O Notation

32 of 59

Counting Operation Cons

Counting operations seems nice, but…

We end up getting long, complicated functions (300x² + 10x + 15)

We really only care about what happens when the input is large

What should we count as an operation?

Is there some way we can

Count operations but not worry about small variations
Emphasize performance scaling when problem size gets arbitrarily large

33 of 59

Big O Notation: O()

Slight tweak to counting operations...we will leave out any multiplicative or lower-order additive terms. This is the “order of growth” of the function.

We often call this “Big O notation” of the runtime. Measures upper bound on order of growth

Used to describe worst case

Occurs often and is bottleneck when program runs
Express rate of program growth relative to input size
Evaluate algorithm, not machine / implementation

34 of 59

Order of Growth

y = n

y = n + 1

y = 2n

y = 0.5n + 1

Multiplicative Constant

35 of 59

Order of Growth

y = n

y = n + 1

y = 2n

y = 0.5n + 1

Lower Order Terms

36 of 59

Order of Growth

Dropping all multiplicative constants and lower order terms, these are all O(n).

y = n

y = n + 1

y = 2n

y = 0.5n + 1

37 of 59

Lower-Order Terms

The “order” of a term is how quickly it grows. The most common ones in order from lower order to higher order

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”

38 of 59

Lower-Order Terms

The “order” of a term is how quickly it grows. The most common ones in order from lower order to higher order

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”

39 of 59

Orders of Growth

Let’s take a look at different orders of growth. The x axis on these charts is the size of input and the y axis is the amount of time taken for that input size. First here we have constant growth, which means that the time needed for the program to run is constant and the amount of time doesn't change as the size of the input gets changed. Next here we have linear growth, which grows in a straight line. Quadratic starts to grow more quickly. Here we also have logarithmic, which is always better than linear because it slows down as we increase the size. n log n or log linear is kind of interesting, but it's a very common complexity for really valuable algorithms in computer science, notably ones for sorting. And it has a nice behavior, sort of between the linear and the quadratic. And lastly here we have exponential, which very quickly escalates in time as our inputs get bigger.

40 of 59

Simplification Examples

Drop lower order terms and multiplicative factors

Focus on dominant term: term that will increase the fastest

2n² + 2n + 2

10¹⁰⁰⁰+ 10n³ + 100n

log(n) + n + 4

0.0001 * n * log(n) + 300n

2n³⁰ + 3ⁿ

2n²O(n²)

10n³O(n³)

n O(n)

0.0001 n log n O(n log n)

3ⁿ O(3ⁿ)

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?

41 of 59

Orders of Growth

The “Order of Growth” of a program looks at the largest factors in the runtime (which part contributes the most to the runtime when input size gets very big).

Doesn’t need to be precise: “order of”, not “exact”, growth

Properties:

Evaluate program’s efficiency when input is very big
Express growth of program’s runtime as input size grows
Put upper bound on growth

Want upper bound (worst case) on growth as function of input size

We want to evaluate efficiency, particularly when the input is very large. What happens when we really scale this up? We want to express the growth of the program's runtime as that input grows. Not the exact runtime, but that notion of it. If we doubled the input, how much longer does it take? What's the relationship between increasing the size of the input and the increase in the amount of time it takes to solve it?

We're going to put an upper bound on that growth. An upper bound means that it’s at least as big as or bigger than the actual amount of time it's going to take. And we’re going to not worry about being precise. We're going to talk about the order of rather than the exact growth. We don't need to know to the femtosecond how long this is going to take, or to the exact number of operations this is going to take.

But, we do want to say things like this is going to grow linearly. We double the size of the input, it doubles the amount of time. Or this is going to grow quadratically. We double the size of the input, it's going to take four times as much time to solve it. Or if we’re really lucky, this is going to have constant growth, meaning no matter how the input changes, it's not going to take any more time.

To do that, we're going to look at the largest factors in the runtime. Which piece of the program takes the most time? And so in orders of growth, we are going to look an upper bound on the growth as a function of the size of the input in the worst case. So here's the notation we're going to use. It's called Big O notation.

42 of 59

Exact Steps vs O()

num1 = n * 2 => 2 ops

num2 = n + 6 => 2 ops

num1 + num2 => 1 op

return => 1 op

total: 6

(Exact) Number of Operations

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

Take the number of operations, and drop multiplicative constants and lower order terms

O(6) = O(1)

Constant runtime

Big O Runtime

43 of 59

Law of Addition

Sequential statements, add

O(f(n)) + O(g(n)) = O(f(n) + g(n))

Example:

def printing(items, digits):

for item in items:

print(item)

for digit in digits:

print(digit)

O(n)

O(n) + O(n)

= O(n + n)

= O(2n)

= O(n)

44 of 59

Exact Steps vs O()

answer = 1 => 1 op

while => loop n times

n > 1 => 1 op

inside while:

answer * n => 1 op

store into answer => 1 op

n - 1 => 1 op

store into n => 1 op

return => 1 op

total: 1 + 5n + 1

(Exact) Number of Operations

def fact_iter(n): answer = 1 while n > 1: answer = answer * n n = n - 1 return answer

Take the number of operations, and drop multiplicative constants and lower order terms

O(1 + 5n + 1) = O(5n + 2) = O(n)

Linear runtime

Big O Runtime

45 of 59

Law of Multiplication

Used with nested loops

O(f(n)) * O(g(n)) = O(f(n) * g(n))

Example:

def printing(grid):

for row in range(len(grid)):

for col in range(len(row)):

print(grid[row][col])

O(n)

O(n) * O(n)

= O(n * n)

= O(n²)

n loops, each O(n)

46 of 59

Exact Steps vs O()

for i in range(n) => n times

for j in range(n) => n times

print(str(i) + str(j)) => 4 ops

==> 4n^2 ops

print(“---”) => 1 op

for k in range(n) => n times

print(k + 2) => 2 ops

==> 2n ops

total: 4n^2 + 1 + 2n

(Exact) Number of Operations

def mystery(n): for i in range(n): for j in range(n): print(str(i), str(j)) print("------") for k in range(n): print(k + 2)

Take the number of operations, and drop multiplicative constants and lower order terms

O(4n^2 + 1 + 2n) = O(n^2 + 1 + n)

= O(n^2)

Quadratic runtime

Big O Runtime

47 of 59

What’s O() Measuring?

Amount of time needed grows as size of input, n, to problem grows
Want to know asymptotic behavior as size of problem gets large
Focus on term that grows most rapidly in sum of terms
Ignore multiplicative and additive constants

48 of 59

Practical Use of Big O

49 of 59

Computing Big O Runtime

Steps:

Count the number of operations
Drop all multiplicative constants and keep only highest order term.

Notice that because you drop lowest order terms, you don’t need to worry about whether to count something as 1 or 2 or 5 operations. 1 == 2 == 5, they are all O(1) (constant time)

50 of 59

Comparing Efficiency of Two Algorithms

Steps:

Compute Big O Runtime of both algorithms
Compare which is higher order. The order Big O Runtime is slower.

51 of 59

Which Input to Evaluate Function Efficiency?

Express efficiency in terms of input size, so need to decide what input is

Could be integer: my_sum(x)
Could be length of list: sum_list(lst)
Decide when multiple parameters: search_for_element(lst, element)

def search_for_element(lst, element): for item in lst: if item == element: return True return False

52 of 59

Terminology Sidenote

Sometimes, you’ll hear Big O / Order of Growth also called “asymptotic runtime”.

An asymptote is a line that approaches a curve but doesn’t meet it.

This is because the Big O runtime of a program is the curve that most closely approaches the actual runtime curve from as N gets very large.

Asymptote

A-sum-ptote

Not - together - fall

Not meeting

53 of 59

Common Operation Runtimes

List or string contains(⋅) check `item in sequence`:

O(n), Because we have to look through each item in the list/string

list.append(item)

O(1). Constant time to add one more item to the end of a list

Indexing: `sequence[index]`:

O(1), Constant time to read the value at particular index in a sequence

Slicing: `sequence[:k]`:

O(k), Linear because slicing makes a new copy in Python

Getting length of something with len(sequence):

O(1), The length is a property of the sequence, quick to look up

Comparing two lists:

O(n), Linear because you have to compare each item to each other item in both lists
n here is the length of both lists

54 of 59

Concatenate +: O(n + k)

sentence = 'I think'

sentence = sentence + 'therefore I am' is O(n + k), where n is size of original string and k is size of string added to original string

Why is + operation O(n + k)?

Computer memory allocates enough space for both strings

Original string gets copied over -> O(n)

String to concatenate gets written -> O(k)

55 of 59

Space Complexity

56 of 59

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 additional space in memory a program uses when it runs.

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

Integers
Booleans
Characters
etc.

57 of 59

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

Creates 2 integers in memory

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

58 of 59

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

59 of 59

Complexity Practice

We’ll see much more complexity practice in classwork and lab this week.