1 of 43

Lecture 13

Complexity

2 of 43

reminder

mic

3 of 43

Measuring efficiency

(how long it takes your program to run)

4 of 43

Algorithmic complexity

Algorithmic complexity is a very important topic in computer science. Knowing the complexity of algorithms allows you to answer questions such as:

�How long will a program run on an input?
�How much space will it take?
�Is the problem even solvable?
�What data structure (ADT) to choose.

5 of 43

Complexity

How well a computer algorithm scales as the amount of data increases.

We need a way to compare algorithms. So we will learn how to create special categories (runtime classes), add algorithms to these categories and compare them instead.

6 of 43

Cars

Automobiles are divided by size into

several categories:

�subcompacts,
�compacts,
�midsize,
�SUV and so on.

These categories provide a quick idea what size car you’re talking about, without needing to mention actual dimensions.

�Similarly, it’s useful to have a shorthand way to say how efficient a computer algorithm is

7 of 43

Lists: One application

8 of 43

List: one application

9 of 43

Lists: Running time

10 of 43

Lists: Running time

11 of 43

Running time: What version of the problem are you analyzing

12 of 43

Analyzing the worst case

def find(lst, toFind):

for i in lst:

if (i == toFind):

return True

return False

How many instructions do you have to execute to find out if the element is in the list in the worst case, if n represents the length of the list?

13 of 43

Analyzing the worst case

def find (lst, toFind):

for i in lst:

if (i == toFind):

return True

return False

def slowFind (lst, toFind):

for i in lst:

print("looking for: " + str(toFind))

if (i == toFind):

return True

return False

Which method is faster?

A: find

B: slowFind

C: They are about the same

14 of 43

Analyzing the worst case

def find (lst, toFind):

for i in lst:

if (i == toFind):

return True

return False

def fastFind(lst, toFind):

return False

Which method is faster?

A: find

B: fastFind

C: They are about the same

15 of 43

16 of 43

Time Complexity

A way of showing how the runtime of function increases as the size of the input increases

17 of 43

Time: Comparing Implementations

Implementations of the same functional abstraction can require different resources
Problem: How many factors does a positive integer n have?
A factor k of n is a positive integer that evenly divides n

def factors(n):

# Slow: Test each k from 1 through n

# Fast: Test each k from 1 to square root n

# For every k, n/k is also a factor!

Question: How many time does each implementation use division?

18 of 43

Def factors(n)

1: Test each k from 1 through n

2: Test each k from 1 to square root n. For every k, n/k is also a factor!

Time (number of divisions)

A: n for (1) n for (2)

B: n² for (1) n^0.5 for (2)

C: n^0.5 for (1) n for (2)

D: n for (1) n^0.5 for (2)

E: None of the above

19 of 43

Comparing Orders of Growth

20 of 43

Properties of Orders of Growth (O vs Theta)

Constants: Constant terms do not affect the order of growth of a process

Logarithms: The base of a logarithm does not affect the order of growth of a process

Lower-order terms: The fastest-growing part of the computation dominates the total

21 of 43

LOGS

22 of 43

Comparing orders of growth (n is the problem size)

23 of 43

Order of Growth of Counting Factors

24 of 43

Order of Growth of Counting Factors

25 of 43

Order of Growth of Counting Factors

26 of 43

Abused Notation

VERY often Big-O is used instead of Big-Theta (in Computer Science).

Not as an upper bound!

27 of 43

Practice

28 of 43

What is the growth rate?

Let R(n) = 100000

What is the growth rate?

A: O(1)

B: O(n)

C: O(log n)

D: O(n log n)

E: O(n²)

29 of 43

What is the growth rate?

Let R(n) = 100000n + n²

What is the growth rate?

A: O(1)

B: O(n)

C: O(log n)

D: O(n log n)

E: O(n²)

30 of 43

What is the growth rate?

Let R(n) = 100000n + n² + n log n

What is the growth rate?

A: O(1)

B: O(n)

C: O(log n)

D: O(n log n)

E: O(n²)

31 of 43

What can you say about these functions?

n, 2n, 3n, 4n, 5n

A: The next one is 6n

B: n is faster than 5n

C: 5n is faster than n

D: All have the same complexity: O(n)

E: Nothing, still waking up

32 of 43

Recognizing the complexity for the code

33 of 43

What is the growth rate?

sum = 0

for i in range(1, n+1):

sum = sum * i

print(i)

A: O(n)

B: O(sqrt(n))

C: O(1)

D: O(n^2)

E: O(log n)

34 of 43

What is the growth rate?

sum = 0

for i in range(1, n+1):

if (i%3 == 0):

sum = sum * i

print(i)

A: O(n)

B: O(1)

C: O(log n)

C: O(n^2)

E: Impossible to calculate

35 of 43

What is the growth rate?

sum = 0

for i in range(1, n+1):

for j in range(1, n+1):

sum = sum * i + j

A: O(n²)

B: O(2^n)

C: O(n)

D: O(log n)

E: O(1)

36 of 43

Useful formula

1 + 2 + 3 + 4 + …… + n =

37 of 43

What is the growth rate?

sum = 0

for i in range(1, n+1):

j = 1

while j <=i:

sum = sum * i + j

j = j + 1

A: O(n²)

B: O(1)

C: O(n)

D: O(log n)

E: O(n log n)

38 of 43

reminder

mic

39 of 43

What is the growth rate?

sum = 0

j = n

while j>1:

print(j)

j = j//2

A: O(1)

B: O(n)

C: O(log n)

D: O(n log n)

E: O(n²)

40 of 43

What is the growth rate?

sum = 0

for i in range(1, n+1):

sum = sum * i

for j in range(1, n+1):

sum = sum + j

A: O(1)

B: O(n)

C: O(log n)

D: O(n log n)

E: O(n²)

41 of 43

What is the growth rate?

sum = 0

j = 1

for i in range(1, n+1):

while j <=i:

sum = sum * i + j

j = j + 1

A: O(n²)

B: O(1)

C: O(n)

D: O(log n)

E: O(n log n)

42 of 43

What is the growth rate?

sum = 0

j = n

while j<=n:

print(j)

j = j*2

A: O(1)

B: O(n)

C: O(log n)

D: O(n log n)

E: O(n²)

43 of 43

What is the growth rate for f2(n)?

def f2(n):

for i in range(1, n+1):

f1(n)

A: O(1)

B: O(n)

C: O(log n)

D: O(n log n)

E: O(n²)

def f1(n):� sum = 0

for i in range(1, n+1):

sum = sum * i

print(i)