Question

PS7, p1-4: I have no clue as to whether these are right or not. Algorithm analysis is still escaping me...

Answer 1

1) What is the computational complexity of fact0? Explain your answer.
def fact0(i):
assert type(i) == int and i >= 0
if i == 0 or i == 1:
return 1
return i * fact0(i-1)

The complexity of fact0 is linear, O(i), because as i increases it has to run through the loop more.

2) What is the computational complexity of fact1? Explain your answer.
def fact1(i):
assert type(i) == int and i >= 0
res = 1
while i > 1:
res = res * i
i -= 1
return res

Same as problem 1. fact1(i) is linear, O(i), because as i increases the function has to run through the loop more.


3) What is the computational complexity of makeSet? Explain your answer.
def makeSet(s):
assert type(s) == str
res = ''
for c in s:
if not c in res:
res = res + c
return res

makeSet(s) is linear?, O(s), because it has to iterate through s and then through res for each c in s even though res increases as s increases (Not super sure on this one.)

4) What is the computational complexity of intersect? Explain your answer.
def intersect(s1, s2):
assert type(s1) == str and type(s2) == str
s1 = makeSet(s1)
s2 = makeSet(s2)
res = ''
for e in s1:
if e in s2:
res = res + e
return res

intersect() is quadratic because first it has to run through makeSet for s1 and s2, and then iterate through s2 at most once for every e in s1.

Answer 2

fact0: The function itself is O(1), but it will call itself i times, so it's doing O(1) things i times, so overall it will be O(i).

fact1: The inside of the loop is O(1), but the loop executes i times. So it's O(i).

makeSet(): This is a little tricky, because it's (implicitly) iterating over res len(s) times, but how big is res? The short answer is that it will be O(len(s)), so the function will be O(len(s)^2). If s only had unique characters, then res will be s at the end of the algorithm, and on the nth trip through the loop we'll check n-1 elements in res. So, what's the sum of the first len(s)-1 integers? It's len(s)(len(s)-1)/2, which becomes O(len(s)^2) (after we ignore the len(s) term and the 1/2 constant factor). It's a little magical how we can treat len(res) as len(s) when it will never be that big. But it will be bounded by that value, and big-O notation is really about bounding.

intersect(): I'm going to use n = len(s1) and m = len(s2). So the first makeSet() call is O(n^2), the second one is O(m^2). And the loop is O(mn). (We found in the answer to the makeSet question that len(res) will be on the order of len(s).) So the total is O(n^2) + O(nm) + O(m^2) which is kinda like O(n^2) + O(2nm) + O(m^2) which is kinda like O(n^2 + 2nm + m^2) which is O((n+m)^2).

They were pretty rigorous, but opaque, in the lecture when they explained how to calculate running time for algorithms. I usually just do it by inspection. Next to each statement write its complexity. Next to loops write how many times it loops. The complexity for the loop will be the product of the complexity of the loop body and the number of times it executes. Add up all those values and find the biggest term. But I don't know how you'd use that to get O(n^2) for makeSet(). I used some assumptions on that that I don't think they went over in lecture.