Algorithm analysis

Introduction

Life’s too easy so let’s complicate it, shall we?

Are you ready to fight the invisible enemy of computational complexity? If not, please read the references first:

• Erik Dassi’s algorithms slides 1 and 2

• Python DS Chapter 2.6: Algorithm analysis

List performance

Python lists are generic containers, they are useful in a variety of scenarios but sometimes their perfomance can be disappointing, so it’s best to know and avoid potentially expensive operations. Table from the Python DS book Chapter 2.6: Lists:

Operation	Big-O Efficiency	Operation	Big-O Efficiency
index []	\(O(1)\)	in (contains)	\(O(n)\)
index assignment	\(O(1)\)	get slice [x:y]	\(O(k)\)
append	\(O(1)\)	del slice	\(O(n)\)
pop()	\(O(1)\)	set slice	\(O(n+k)\)
pop(i)	\(O(n)\)	reverse	\(O(n)\)
extend(lb)	\(O(m)\)	la + lb	\(O(n+m)\)
insert(i,item)	\(O(n)\)	sort	\(O(n \log{n})\)
del operator	\(O(n)\)	multiply	\(O(nk)\)
remove	\(O(n)\)	min	\(O(n)\)
iteration	\(O(n)\)	max	\(O(n)\)
len(lst)	\(O(1)\)	sum	\(O(n)\)
equality	\(O(n)\)

Fast or not?

Given a list x of \(n\) characters, for each of the following expressions, try giving the complexity:

1. x[n // 2]
   

2. x[n // 2] = 'd'
   

3. x.append('c')
   

4. x.insert(0, 'd')
   

5. x + x
   

6. x[3:5]
   

7. x.sort()
   

8. len(x)
   

9. x.pop(1)
   

10. x.pop(-1)
    

11. 'z' in x
    

12. x.extend(1000)
    

13. y = [c for c in x]
    

14. list(range(n)) == list(range(n))
    

Sublist iteration performance

get slice time complexity is \(O(k)\), but what about memory? It’s the same!

So if you want to iterate a part of a list, beware of slicing! For example, depending pn Python version you have, slicing a list like this can occupy much more memory than necessary:

                 #                               memory occupied
r = range(1000)  # Python 2 creates a list:           O(n)
                 # Python 3 creates a 'range' object: O(1)

#                                   same for range slices: memory occupied
print([2*y for y in r[100:200]])  #  r[100:200] Python 2        O(k)
                                  #             Python 3        O(1)

[200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 224, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276, 278, 280, 282, 284, 286, 288, 290, 292, 294, 296, 298, 300, 302, 304, 306, 308, 310, 312, 314, 316, 318, 320, 322, 324, 326, 328, 330, 332, 334, 336, 338, 340, 342, 344, 346, 348, 350, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372, 374, 376, 378, 380, 382, 384, 386, 388, 390, 392, 394, 396, 398]

The reason is that, according to your Python interpreter, slicing like r[100:200]at loop start can create a new list. If we want to explicitly tell Python we just want to iterate through a sequence, we can use the so-called itertools. In particular, the islice method is handy, we can rewrite the list comprehension above with it like this:

import itertools

r = range(1000)

print([2*y for y in itertools.islice(r, 100, 200)])

[200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 224, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254, 256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276, 278, 280, 282, 284, 286, 288, 290, 292, 294, 296, 298, 300, 302, 304, 306, 308, 310, 312, 314, 316, 318, 320, 322, 324, 326, 328, 330, 332, 334, 336, 338, 340, 342, 344, 346, 348, 350, 352, 354, 356, 358, 360, 362, 364, 366, 368, 370, 372, 374, 376, 378, 380, 382, 384, 386, 388, 390, 392, 394, 396, 398]

Some formulas

\[\begin{split}\begin{gather*} & & & & && \text{Complexity}\\ 1 + 2 + 3 + \dots + n & = & \sum_{i=1}^n{i} & = & \frac{n^2+n}{2} && O(n^2) \\ 1^2 + 2^2 + 3^2 + \dots + n^2 & = & \sum_{i=1}^n{i^2} & = & \frac{n(n+1)(2n+1)}{6} && O(n^3) \\ \end{gather*}\end{split}\]

Lists - exercises

Who’s the fastest? Let’s start the racing game!

For each of the following code samples, try giving the worst-case running time in Big O notation.

Exercise - rollsroyce

• x : int

• lst : list of \(n\) integers

def rollsroyce(x, lst):
    return x in lst

Show answer

ANSWER: \(O(n)\) if we assume integer comparison is \(O(1)\), which typically is the case in most programs we write. Note that differently from most programming languages, Python actually allows unbounded integers, but for the purposes of this course you can safely consider occupied memory for integers as constant.

Exercise - honda

• x : list of \(m\) elements

• lst: list of lists with \(n\) rows and \(m\) columns

def honda(x, lst):
    return x in lst

Show answer

ANSWER: \(O(n m)\)

In this case Python has to do a lot of work in performing comparisons:

      0,1,2,3,4 ... m
   x=[3,4,2,6,7,2,6,8]

lst=[[0,0,0,0,0,0,0,0],  # 0
     [1,1,1,1,1,1,1,1],  # 1
     [2,2,2,2,2,2,2,2],  # 2
     [3,3,3,3,3,3,3,3],  # 3
     [4,4,4,4,4,4,4,4],  # 4
     [5,5,5,5,5,5,5,5],  # 5
     [6,6,6,6,6,6,6,6],  # 6
     [3,4,2,6,7,2,6,8],  # n  <--- worst case scenario: matching list at the end
    ]                              (or not present at all),
                                   need to compare all elements in all rows

Exercise - lamborghini

• lst : list of \(n\) elements

• m : int

def lamborghini(lst, m):
    return lst * m

Show answer

ANSWER: \(O(n*m)\)

>>> lamborghini(['a','b','c'], 5)

#|-----n------|-------n------|-------n------|-------n------|-------n------|
['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c']

Exercise - maserati

• lst : list of \(n\) elements

• m : int

def maserati(lst, m):
    return [m for el in lst]

Show answer

ANSWER: \(O(n)\)

List comprehension:

• visit lst: cost is \(O(n)\)

• generate a new list: in this case places constants in each cell, so cost is \(O(n)\)

\(O(n + n)=O(2n)=O(n)\)

Exercise - toyota

• lst : list of \(n\) elements

• m : int

HINT: try rewriting code as a for, then add costs

def toyota(lst, m):
    return [lst[:m] for el in lst]

Show answer

ANSWER: \(O(n m)\)

We can rewrite the code like this:

def toyota2(lst, m):
    ret = []                 #  1
    for el in lst:           #  n iterations
        sub = lst[:m]        #      building m cells
        ret.append(sub)      #      1
    return ret               #  1

\[\begin{split}\begin{align} O(1 + n(m + 1) + 1) &= O(1 + nm + n + 1)\\ &= O(nm + n )\\ &= O(nm)\\ \end{align}\end{split}\]

Exercise - mercedes

• lst : list of \(n\) elements

def mercedes(lst):
    for i in range(len(lst)):
        lst.append('z')
    return lst

Show answer

ANSWER: \(O(n)\)

def mercedes(lst):
    for i in range(len(lst)):      # n iterations
        lst.append('z')            #     1
    return lst                     # 1

\(O(n*1 + 1) = O(n)\)

Note append has an amortized cost of \(O(1)\), so \(n\) calls to append give \(O(n)\)

Exercise - acura

• lst : list of \(n\) elements

• m : int

def acura(lst, m):
    return lst[:m] + lst

Show answer

ANSWER: \(O(n)\)

We can rewrite like this:

def acura2(lst, m):
    sub = lst[:m]     # m
    ret = sub + lst   # m + n
    return ret        # 1

\(O(m + m + n + 1) = O(n)\) in this case because the sublist is at most n long.

Exercise - alfaromeo

• lst : list of \(n\) elements

def alfaromeo(lst):
    return [(lst[0] + lst[-1]) for i in range(len(lst))]

Show answer

ANSWER: \(O(n)\)

We can rewrite it like this:

def alfaromeo2(lst):
    ret = []                     # 1
    for i in range(len(list)):   # n iterations
        sub = lst[0] + lst[1]    #     access lst[0] : 1
                                 #     access lst[1] : 1
                                 #     build sub : 2
        ret.append(sub)          #     1
    return ret                   # 1

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

Exercise - jeep

lst : list of \(n\) elements

def jeep(lst):
    return [lst[:i] for i in range(1, len(lst))]

Show answer

ANSWER: \(O(n^2)\)

jeep(['a','b','c','d','e','f','g'])

Building lists:

a            1
ab           2
abc          3
abcd         4
abcde        .
abcdef       .
abcdefg      n
1234..n

It looks like a square triangle with side n, so it takes \(\displaystyle\sum_{i=1}^n{i}=\frac{n^2+n}{2}\) operations

Then it collects the \(n\) sublists into one big list, costing \(n\), so \(\displaystyle O\left(\frac{n^2+n}{2} + n\right) = O(n^2/2) = O(n^2)\)

Exercise - chevrolet

lst : list of \(n\) elements

def chevrolet(lst):
    for i in range(len(lst)):
        lst.insert(0,'z')
    return lst

Show answer

ANSWER: \(O(n^2)\)

Calling insert inside the list at the beginning takes \(O(n)\) since Python has to shift all the following elements of one position. In this case at each call the list grows, so we have a situation like this:

>>> chevrolet(['a','b','c','d','e'])

# abcde
# zabcde      n    1
# zzabcde     n+1  2
# zzzabcde    n+2  3
# zzzzabcde   n+3  4
# zzzzzabcde  n+4  n
# |-n-||-n-|

It looks like a kind of \(n*n\) block with a triangle attached to it, thus:

\[\begin{align} O(n^2 + \frac{n^2 + n}{2}) = O(n^2) \end{align}\]

Exercise - kia

lst : list of \(n\) characters

1. What is the worst case complexity?

2. What is the best case complexity?

def kia(lst):
    for i in range(len(lst) // 2):
        lst.remove('c')

Show answer

ANSWER:

def kia(lst):
                                       #  len(lst)//2 calculation :  1
    for i in range(len(lst) // 2):     #  n / 2  iterations
        lst.remove('c')                #       n

1. worst case: if list has at least \(n/2\) 'c', we have \(O(1 + n/2 * n) = O(n^2/2) = O(n^2)\)

Note remove only removes the first element found, and raises an exception if not found. So to actually have O(n^2) complexity without the function terminating early, we would need to be in worst case scenario where we have n//2 characters 'c' in our list

2. best case: no 'c' charactersare present, so remove searches all list in \(O(n)\) and terminates immediately by raising an exception

Exercise - aston_martin

lst: list of \(n\) elements

def aston_martin(lst):
    ret = []
    if lst[0] > 5:

        for i in range(len(lst)):
            for j in range(len(lst)):
                ret.append(lst[i])
    else:
        for i in range(len(lst)):
            ret.append(lst[i] * 2)
    return ret

Show answer

ANSWER: \(O(n^2)\)

def aston_martin(lst):
    ret = []                             #   1
    if lst[0] > 5:                       #   1
                                         #   THEN branch:
        for i in range(len(lst)):        #       n iterations
            for j in range(len(lst)):    #           n iterations
                ret.append(lst[i])       #               append: 1, element access: 1
    else:                                #   ELSE branch:
        for i in range(len(lst)):        #       n iterations
            ret.append(lst[i] * 2)       #            access:1 , mul: 1, append: 1
    return ret                           #   1

\(O(2 + \max{(n*n*2, n*3)} + 1) = O(n^2)\)

Exercise - subaru

• mat : list of \(n\) lists of \(n\) elements each

1. What’s the complexity?

2. Follow up: Can you write a more perfomant version?

def subaru(mat):
    n = len(mat)
    ret = []
    for i in range(n):
        for j in range(n):
            if i == n - j - 1:
                ret.append(mat[i][j])
    return ret

Show answer

ANSWER:

1. it calculates the anti-diagonal in \(O(n^2)\)

def subaru(mat):
    n = len(mat)                        # 1
    ret = []                            # 1
    for i in range(n):                  # n iterations
        for j in range(n):              #   n iterations
            if i == n - j - 1:          #     minuses: 1 + 1, comparison: 1
                ret.append(mat[i][j])   #     1
    return ret                          # 1

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

subaru([[1,4,5,7],
        [1,4,9,5],
        [3,4,8,2],
        [2,6,1,5]])
[7, 9, 4, 2]

2. Since it’s the anti-diagonal, we are basically extracting a line out of the matrix so we should try devising a linear time \(O(n)\) algorithm, like this one:

def subaru2(mat):
    n = len(mat)                          # 1
    ret = []                              # 1
    for i in range(n):                    # n iterations
        ret.append(mat[i][n - i - 1])     #     append: 1 ,  minuses: 2, append: 1
    return ret                            # 1

subaru2([[1,4,5,7],
             [1,4,9,5],
             [3,4,8,2],
             [2,6,1,5]])

[7, 9, 4, 2]

Exercise - dodge

• mat : list of \(n\) lists of \(m\) columns

def dodge(mat):
    n = len(mat)
    m = len(mat[0])
    ret = []
    for i in range(n):
        for j in range(1,m):
            if max(mat[i][:j]) == 3:
                ret.append(mat[i][j])
    return ret

Show answer

ANSWER: \(O(nm^2)\)

We can rewrite the function like this:

def dodge(mat):
    n = len(mat)                        # 1
    m = len(mat[0])                     # access: 1, len: 1
    ret = []                            # 1
    for i in range(n):                  # n iterations
        for j in range(1,m):            #    m iterations
            sliced = mat[i][:j]         #       from 1 to m-1  ~ m
            mx = max(sliced)            #       from 1 to m-1  ~ m
            if mx == 3:                 #       1
                ret.append(mat[i][j])   #       append: 1 , access 1
    return ret                          # 1

\(O(4 + n*m*(m + m + 3) + 1) = O(nm^2 + 3nm) = O(nm^2)\)

Exercise - lotus

lst : list of \(n\) elements

def lotus(lst):
    while len(lst) > 0:
        el = lst.pop(len(lst) // 2)
        ret.append(el)
    return ret

Show answer

ANSWER: \(O(n^2)\)

def lotus(lst):
    while len(lst) > 0:               # n iterations
        el = lst.pop(len(lst) // 2)   #     middle pop: costs n, n-1, n-2, ..... 1   ~ n
        ret.append(el)                #     1
    return ret                        # 1

\(O(n * (n + 1) + 1) = O(n^2 + n) = O(n^2)\)

Exercise - jaguar

• mat : list of \(n\) lists of \(m\) columns

def jaguar(mat):
    n = len(mat)
    m = len(mat[0])
    for i in range(1, n):
        if mat[i-1][0] in mat[i]:
            for j in range(n-1,0,-1):
                mat[j] = [2*x for x in mat[j]]

    return mat

Show answer

ANSWER: \(O(n^2m)\)

def jaguar(mat):
    n = len(mat)                                # 1
    m = len(mat[0])                             # access: 1 , len: 2
    for i in range(1, n):                       # n - 1 iterations
        if mat[i-1][0] in mat[i]:               #    if: 1 (in worst case always true)
                                                #    in: m
            for j in range(n-1,0,-1):           #    n - 1 iterations
                mat[j] = [2*x for x in mat[j]]  #        m iterations
                                                #             2*x:    1
                                                #        assignment: 1
    return mat                                  # 1

\(O(4 + (n-1)(m+1 + (n-1)(m*1 + 1)) + 1)\)

\(= O(4+ n(m + nm))\)

\(= O(nm + n^2m)\)

\(= O(n^2m)\)

Exercise - hyundai

• lst : list of \(n\) elements

• m: integer, \(0 <= m <= n\)

def hyundai(lst, m):

    lb = ['a' in range(m)]

    lb.extend(lst)

    for i in range(m):
        lb.remove('a')

Show answer

ANSWER: \(O(m^2n)\)

def hyundai(lst, m):

    lb = ['a' in range(m)]     # m

    lb.extend(lst)             # n

    for i in range(m):         # m
        lb.remove('a')         #     m + n, m-1 + n, m-2 + n, .... 3 + n, 2 + n, 1 + n
                               #     we can roughly estimate ~ m + n

\(O(m + n + m(m+n)) = O(m+n+m^2n + mn) = O(m^2n)\)

Note remove removes the first element it finds, and upon unsuccessful search throws an exception. In order for the function to terminate properly, it would need to find 'a' character for m times, and each call will always take \(O(m + n)\) even if searched chars are at the beginning, as element removal requires Python to shift most elements of the list in memory anyway.

Exercise - buick

lb : list of \(n\) positive integers

HINT: Try giving a tight complexity bound for the function, considering we assume lb is only made of positive integers

def buick(lb):
    la = []
    n = len(lb)
    while len(lb) > 0:
        el = lb.pop()
        la.insert(0,el)
        if sum(la) == 10:
            for i in range(n):
                for j in range(n):
                    la[0] += 1


    return la

Show answer

ANSWER: \(O(n^2)\)

def buick(lb):
    la = []                                        # 1
    n = len(lb)                                    # 1
    while len(lb) > 0:                             # n iterations (lb will be popped until empty)
        el = lb.pop()                              #    pop: 1  + assignment: 1
        la.insert(0,el)                            #    from 1 to n
        if sum(la) == 10:                          #    sum: from 1 to n  + if: 1
            for i in range(n):                     #    n iterations
                for j in range(n):                 #       n iterations
                    la[0] += 1                     #            1
                                                   #       but note because of the 'if' this double for
                                                   #       is executed *at most once per function call*
    return la                                      # 1

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

NOTE: last \(n^2\) is for the expensive double for and was put outside the while cycle computation for the following reason: from function text we know it’s already unlikely la sum is 10. As soon as it becomes 10, we are going to add stuff to it (we assume all input numbers are positive). Thus, the if will be entered at most once per function call.

buick([1,9,8,1,4,7,2])
buick([1,9,8,1,4,7,3]) # triggers the double for

Exercise - saab

lst : list of \(n\) integers

1. To solve this properly you will need to resort to some classical analysis:

1. for determining worst case, try proving the sum is less than another sum

2. to see if the bound is tight, try determining the best case complexity \(\Omega\) by proving that the sum made by half of the terms (which half?) is greater than another sum: you should get the same result as worst case thus demonstrating you’ve got the \(\Theta\) complexity.

2. Can we write a much faster function?

def saab(lst):

    for i in range(1, len(lst)):
        lst.sort(lst[0:i])

Show answer

ANSWER:

def saab(lst):

    for i in range(1,len(lst)):   # n iterations
        lst.sort(lst[0:i])        #      lst[0:i]: 0+1+2+3+...+ n
                                  #      sort    : 1log1 , 2log2 , 3log3 , ... , nlogn

The sort line is a bit tricky. Let’s try a rough upper bound:

\[\sum_{i=1}^n{i~\log{i}} \leq n(n~\log{n}) \leq n^2~\log{n} = O(n^2~\log{n})\]

Is it tight? We need to verify if lower bound is at least \(\Omega(n^2~\log{n})\)

There are many methods, let’s use classical analysis and try to majorate the sum by picking half of the summation interval:

\[\begin{split}\begin{align*} \sum_{i=1}^n{i~\log{i}} &\geq \sum_{i=n/2}^n{i\log{i}} \\ &\geq \frac{n}{2} \left( \frac{n}{2} \log\frac{n}{2}\right) \\ &\geq \frac{n^2}{4} \left(\log{n}-\log{2}\right) \\ &\geq \frac{n^2}{4} \left(\log{n} - 1\right) \end{align*}\end{split}\]

We see that even if we limit ourselves to sum half of the interval, the summation always exceeds the \(\Omega(n^2\log{n})\) factor, hence a tight bound for complexity is \(\Theta\left({n^2\log{n}}\right)\)

2. all this repeated sorting is of course useless, it’s sufficient to just call sort once:

def saab_fast(lst):

    lst.sort(lst)

which takes \(O(n\log{n})\)

Sets performance

Let’s review set average operations costs from Python official wiki:

Operation	Big-O Efficiency	Operation	Big-O Efficiency
x in s	\(O(1)\)	union sa | sb	\(O(n + m)\)
intersection sa & sb	\(O(min(n,m))\)	difference sa-sb	\(O(n)\)
sa.difference_update(sb)	\(O(m)\)	set(sequence)	\(O(n)\)
len(s)	\(O(1)\)	min(s)	\(O(n)\)
sum(s)	\(O(n)\)	max(s)	\(O(n)\)

Sets are pretty fast but notice in degenerate cases we might still get \(O(n)\) complexities instead of \(O(1)\) (like when there too many keys collisions or with ill-devised hashing functions). For the purposes of this course but won’t consider those occurrences.

WARNING: LOOPING ON SETS IS SLOW!

A loop typically takes \(O(n)\), but sets were designed to offer \(O(1)\) read / write access by using the square brackets operator [] or containment operator in.

If you’re thinking about using a loop, always ask yourself if you could rewrite your algorithm in some other way

HAVE YOU READ THE WARNING ABOVE??

People who don’t understand it are usually condemned to a dreaded yet-another-retake-of-sciprog exam. You’re warned.

Sets - exercises

Find the worst case compexity in Big-O notation for each of the following exercises.

Exercise - land_rover

• sa : set of \(n\) integers

• sb : set of \(m\) integers

def land_rover(sa, sb):
    return [el in sa for el in sb]

Show answer

ANSWER: \(O(m)\)

def land_rover(sa, sb):
    return [el in sa for el in sb]          # list comprehension: m iterations
                                            #     in set: 1

Exercise - volkswagen

• la : list of \(n\) integers

• lb : list of \(m\) integers

def volkswagen(la, lb):
    sa = set(la)
    sc = set()
    for el in lb:
        if el % 2 != 0:
            sc.add(el)
    return (sa | sc) - (sa & sc)

Show answer

ANSWER: \(O(n+m)\)

def volkswagen(la, lb):
    sa = set(la)                     # n
    sc = set()                       # 1
    for el in lb:                    # m iterations
        if el % 2 != 0:              #     1
            sc.add(el)               #     1
    return (sa | sc) - (sa & sc)     # union |       : n+m
                                     # intersection &: min(n,m)
                                     # difference -  : left term costs n+m
                                     #                 NOTE: sc can have at most m elements

\(O(n+1+m(1+1) + (n+m)+min(n,m)+n+m)=O(n+m)\)

Exercise - pontiac

mat : list of \(n\) lists of \(m\) integers

def pontiac(mat):
    ret = []
    sets = [set(row) for row in mat]
    for i in range(len(mat)):
        for s in sets:
            if mat[i][0]*2 in s:
                ret.append(mat[i][0])
    return ret

Show answer

ANSWER: \(O(mn + n^2)\)

def pontiac(mat):
    ret = []                                 # 1
    sets = [set(row) for row in mat]         # m * n (creating a set of m elements n times)
    for i in range(len(mat)):                # n iterations
        for s in sets:                       #    n  iterations
            if mat[i][0]*2 in s:             #        set in:  1  , mat access: 1 , mul: 1
                ret.append(mat[i][0])        #        access: 1 , append: 1
    return ret                               # 1

pontiac([
    [3,5,2,5,7,2],
    [2,2,8,7,3,4],
    [4,1,4,1,5,6],
])

\(O(1 + mn + n(n(3+2)))=O(mn + n^2)\)

Exercise - volvo

• la : list of \(n\) integers

• lb : list of \(m\) integers

def volvo(la, lb):
    ret = set(lb)
    for i in range(len(la)):
        sli = la[i+1:]
        if la[i] in sli:
            ret.add(la[i])
        for el in la:
            if el in ret:
                ret.add(el*2)
    return ret

Show answer

ANSWER: \(O(n^2 + m)\)

def volvo(la, lb):
    ret = set(lb)                 #  m
    for i in range(len(la)):      #  n iterations
        sli = la[i+1:]            #      n-1, n-2,  ...... , 1              ~ n
        if la[i] in sli:          #      in list:  n-1 , n-2 , ...... , 1   ~ n
            ret.add(la[i])        #      la access: 1, set add: 1
        for el in la:             #      n iterations
            if el in ret:         #          in set: 1
                ret.add(el*2)     #          set add: 1,  mul: 1
    return ret                    #  1

volvo([7,6,8,4,6,7,6], [6,9,2,5,3,4,6])

\(O(m+n(n+n+2+n(1+2))+1)\)

\(= O(m+n(2n+3n+2))\)

\(= O(m+n^2+n)\)

\(=O(n^2 + m)\)

Exercise - chrysler

la: list of \(n\) integers

HINT 1: remember the sum of first \(n\) integers is \(\displaystyle\sum_{i=1}^n{i}=\frac{n^2+n}{2}\)

HINT 2: remember the sum of first \(n\) squared integers is \(\displaystyle\sum_{i=1}^n{i^2}=\frac{n(n+1)(2n+1)}{6}\)

def chrysler(la):

    s = {0}
    lb = []
    for i in range(len(la)):
        lb.extend([la[i]] * i)
        if min(s) < 20:
            s = {x for x in la}
        s = s | set(lb)
    return s

Show answer

ANSWER: \(O(n^3)\)

def chrysler(la):

    s = {0}                            #   1
    lb = []                            #   1
    for i in range(len(la)):           #   n iterations
        lb.extend([la[i]] * i)         #       list replication: 1 , 2 , 3 , .... , n  ~ n
                                       #       extend:           1 , 2 , 3 , .... , n  ~ n
        if min(s) < 20:                #       min: 1 , 2 , 3 , .... , n   ~ n
            s = {x for x in la}        #       n
        s = s | set(lb)                #       f(i)  <--- to be determined later ...
    return s                           #   1

Let \(k\) be the number of distinct elements of la: given how the algorithm is structured, in worst case s ends up containing \(k\) elements.

Let’s try calculating \(f(i)\): even we already know s in the end will always contain k elements, Python will still need to convert lb to a set, and then do the union with s. At each iteration, the number of items to scan in lb will grow non-linearly:

                 #                                sum of first i      iteration
                 #  union      set conversion     natural numbers         i
s = s | set(lb)  #  k + 1      +1                 = k + 1 + (1^2+1)/2     1
                 #  k + 2      +1+2               = k + 2 + (2^2+2)/2     2
                 #  k + 3      +1+2+3             = k + 3 + (3^2+3)/2     3
                 #      .            .                                    .
                 #  k + k            .                                    .
                 #  k + k      +1+2+3+ .. +n      = k + k + (n^2+n)/2     n

Considering the whole \(n\) iterations, we will get a sum of increasing squares, so that row alone will cost \(g(n)\) like this:

\[\begin{split}\begin{align*} g(n) &= \sum_{i=1}^n{f(i)} \\ &= \sum_{i=1}^n{\left(k + \min (i,k) + \frac{i^2+i}{2}\right) } \\ &= \sum_{i=1}^n{k} + \sum_{i=1}^n {\min (i,k)} + \frac{1}{2} \sum_{i=1}^n{i^2} + \frac{1}{2} \sum_{i=1}^n{i} \\ &\leq n k + n k + \frac{1}{2} \frac{n(n+1)(2n+1)}{6} + \frac{1}{2} \frac{n^2 + n}{2} \\ &\leq nk + n k + \frac{2n^3 + n^2 + 2n^2 + n}{12} + \frac{n^2+n}{4} \end{align*}\end{split}\]

Since \(k \leq n\) , the heavier term is \(n^3\) thus we conclude:

\[O(g(n)) = O(nk + n^3) = O(n^3)\]

Plugging \(g(n)\) in the whole algorithm context, we get:

\[O(2+n(n + n + n + n) + g(n) + 1)= O(n^2 + n^3) = O(n^3)\]

Dictionaries performance

Let’s review dictionary operations costs from the Python DS book Chapter 3.7: Dictionaries:

Operation	Example	Big-O Efficiency
key containment	key in d	\(O(1)\)
read a value given a key	d[key]	\(O(1)\)
write an association	d[key] = value	\(O(1)\)
delete an association	del d[key]	\(O(1)\)
iterating keys / 1	for key in d:	\(O(n)\)
iterating keys / 2	for key in d.keys():	\(O(n)\)
iterating values	for value in d.values():	\(O(n)\)
iterating associations	for key,value in d.items():	\(O(n)\)
shallow copy	d.copy()	\(O(n)\)

Dictionaries are pretty fast but notice in degenerate cases we might still get \(O(n)\) complexity instead of \(O(1)\), like when there too many keys collisions or with ill-devised hashing functions. For the purposes of this course but won’t consider those occurrences.

WARNING: LOOPING ON DICTIONARIES IS SLOW!

A loop typically takes \(O(n)\), but dictionaries were designed to offer \(O(1)\) read / write access by using the square brackets operator [] or containment operator in.

If you’re thinking about using a loop, always ask yourself if you could rewrite your algorithm in some other way

HAVE YOU READ THE WARNING ABOVE??

People who don’t understand it are usually condemned to a dreaded yet-another-retake-of-sciprog exam. You’re warned.

Dictionaries - exercises

Find the worst case compexity in Big-O notation for each of the following exercises.

Exercise - tesla

• x : int

• d: dictionary with \(n\) key/value mappings

def tesla(x, d):
    return x in d

Show answer

ANSWER: \(O(1)\)

Searching keys in dictionaries is very fast because of hashing.

Exercise - bmw

• d : dictionary of \(n\) key/value mappings

• el : int

def bmw(d, el):

    if el in d:
        return d[el]

    return None

Show answer

ANSWER: \(O(1)\)

def bmw(d, el):

    if el in d:           # in dict: 1
        return d[el]      # dict access: 1 , return 1

    return None           # 1

Exercise - nissan

• d : dictionary of \(n\) key/value mappings

• el : int

Does this code behaves differently from code before? Compare complexity.

def nissan(d, el):

    for k in d:
        if el == k:
            return d[el]

    return None

Show answer

ANSWER: \(O(n)\)

If we’re lucky, we will find the object very soon, but if we aren’t we will have to scan all of the dictionary, so worst case complexity is \(O(n)\)

Exercise - ferrari

• x : int

• d: dictionary with \(n\) key/value mappings

Find the complexity and then ask yourself if we can do any better.

def ferrari(x, d):
    return x in d.values()

Show answer

ANSWER: \(O(n)\)

Value access is sequential, as they may contain duplicates or be mutable.

Exercise - bentley

• x : int

• d : dictionary with \(n\) key/value mappings

def bentley(x, d):

    return x,x in d.items()

Show answer

ANSWER: \(O(n)\)

.items() return a sequence, which needs to be scanned one by one.

Exercise - mclaren

• d : dictionary of \(n\) key/value mappings

• k : int

def mclaren(d,k):
    ret = []
    for i in range(k):
        if i in d:
            ret.append(d[i])
    return ret

Show answer

ANSWER: \(O(k)\)

def mclaren(d,k):              #
    ret = []                   # 1
    for i in range(k):         # k iterations
        if i in d:             #     1  (search in keys)
            ret.append(d[i])   #     dictionary access: 1  ,  append: 1
    return ret                 # 1

\(O(1 + k(1 + 2)) = O(k)\)

Under normal loads complexity here does not depend on dictionary size

Exercise - fiat

• d : dictionary of \(n\) key/value mappings

• k : int

Compare this function to previous one. Is there any difference?

def fiat(d,k):
    lst = list(d.items())
    ret = []
    for i,v in lst:
        if i >= 0 and i < k:
            ret.append(d[i])
    return ret

Show answer

ANSWER: \(O(n)\)

def fiat(d,k):
    lst = list(d.items())         #  list: n , items: n
    ret = []                      #  1
    for i,v in lst:               #  n iterations
        if i >= 0 and i < k:      #     comparisons: 1 + 1 , and: 1
            ret.append(d[i])      #     dictionary access: 1 , append: 1
    return ret                    #  1

This function does the same same as the previous one, but performance is different (if \(k < n\)). Converting all items to list always takes an amount of time proportinal to all key/mappings in the dictionary, so if we later search in the list we are defeating the purpose of dictionaries, which should be fast searching !

\(O(2n + 1 + n(3 + 2)) + 1) = O(n)\)

Exercise - mustang

• d : dictionary of \(n\) key/value mappings

• lst : list of \(m\) integers

def mustang(d, lst):

    ret = {}
    for el in lst:

        if el in d:
            if el in list(d.values()):
                ret[el] = True
        else:
            ret[el] = False
    return ret

Show answer

ANSWER: \(O(mn)\)

def mustang(d, lst):

    ret = {}                                 #  1
    for el in lst:                           #  m iterations
        if el in d:                          #  1
                                             #  THEN branch
            if el in list(d.values()):       #        values(): n ,  list : n, in list: n
                ret[el] = True               #        1
        else:                                #  ELSE branch
            ret[el] = False                  #     1
    return ret                               #  1

\(O(1 + m(1 + max(3n + 1, 1)) + 1) = O(m + m(3n+1)) = O(m n + m) = O(mn)\)

Recursion

References:

• Andrea Passerini slides on recursion theory

• Recursion worksheets on sciprog

When confronted with a problem, we can try to solve it by splitting its dimension in half (or more), look for solutions in each of the halves and then decide what to do with the found solutions, if any.

Several cases may occur:

1. No solution is found

2. One solution is found

3. Two solutions are found

case 1): we can only give up

case 2): we have only one solution, so we can just return that one

case 3): we have two solutions, so we need to decide what is the purpose of the algorithm

Is the purpose to …

• find all possible solutions? Then we return both of them.

• find the best solution, according to some measure of ‘goodness’? Then we measure each of the solutions and give back the highest scoring one.

• always provide a combination of existing solutions, according to some combination method? Then we combine the found solutions and give them back

The Master Theorem

To get a precise calculation of complexity of recursive algorithms, let’s recall the Master Theorem:

Let \(a\) and \(b\) two integer constants such that \(\normalsize a \geq 1\) and \(\normalsize b \geq 2\), and let \(\normalsize c, \beta\) be two real constants such that \(\normalsize c > 0\) and \(\normalsize \beta \geq 0\). Let \(\normalsize T(n)\) be defined by the following recurrence:

\[\begin{split}\large T(n) = \begin{cases} a T(n/b)+cn^\beta & n > 1 \\ \Theta(n) & n \leq 1 \end{cases}\end{split}\]

Given \(\large {\alpha = \frac{\log{a}}{\log{b}} = \log_b{a}}\), then:

\[\begin{split}\large T(n) = \begin{cases} \Theta(n^\alpha) & \alpha > \beta \\ \Theta(n^\alpha \log{n}) & \alpha = \beta \\ \Theta(n^\beta) & \alpha < \beta \end{cases}\end{split}\]

The theorem covers cases when:

• input of size \(n\) is split in \(b\) subproblems

• the algorithm is applied recursively \(n\) times

• \(\normalsize cn^\beta\) is the cost of the algorithm after the recursive steps

Recursion - exercises

Exercise - yamaha

1. What does this function do?

2. What’s the time complexity? Give both an informal argument and a formal one using the Master Theorem.

• lst: a list of \(n\) numbers

• i: an index from 0 to \(n\) included

level is the recursion level, we can use it to help ourselves while debugging

def yamaha(lst, i, level=0):
    print('  ' * level, lst)
    print('  ' * level, i)

    if i == 0:
        return 0
    else:
        q = lst[i-1] + yamaha(lst, i-1, level + 1)
        print('  ' * level, q)
        return q

print(yamaha([5,7,2,9], 4))

 [5, 7, 2, 9]
 4
   [5, 7, 2, 9]
   3
     [5, 7, 2, 9]
     2
       [5, 7, 2, 9]
       1
         [5, 7, 2, 9]
         0
       5
     12
   14
 23
23

Show answer

ANSWER:

Informal argument: Since this is a simple function, just by inspecting it we can conclude it sums all the numbers. Since the list is always completely traversed we can state the complexity is \(\Theta(n)\)

Notice that as all recursive functions in Python, we would be also limited by the amount of recursive calls that Python imposes, which was fixed by language designers to 1000 (Python is not a language optimized for recursive calls).

Formal argument using the Master Theorem (Required during the exam!): TODO

Exercise - cadillac

Look at the following code:

1. To get a better understanding, try adding an integer optional parameter level=0 with the recursion level, and print the function passages indented according to the recursion level

2. What is this function doing?

3. Is recursion eventually terminating after some time?

4. What’s the time complexity? Try giving both an informal argument and a precise one using the Master Theorem

• lst : list of \(n\) integers

def cadillac(lst):

    if len(lst) == 0:
        return 0

    if len(lst) == 1:
        return lst[0]

    k = len(lst) // 2
    p = cadillac(lst[:k])
    q = cadillac(lst[k:])
    return p + q

a) Solution for code with added debug prints and level=0 param:

Show solution

def cadillac(lst, level=0):

    print('    '*level,lst)

    #  By repeatedly reducing input size, do we eventually end up in a branch with a return?
    #  YES !
    if len(lst) == 0:                 # 1
        return 0                      # 1

    #  By repeatedly reducing input size, do we eventually end up in a branch with a return?
    #  YES !
    if len(lst) == 1:                 # 1
        return lst[0]                 # 1

    # Are we reducing input size when calling cadillac?
    # YES !
    k = len(lst) // 2                 # 1
    p = cadillac(lst[:k], level + 1)   # slice creation: n/2  + recursive call cost:?
    print('    '*level, 'p=', p)
    q = cadillac(lst[k:], level + 1)   # slice creation: n/2  + recursive call cost:?
    print('    '*level, 'q=', q)
    return p + q                      # 1


res = cadillac([4,2,6,2,9,4,8,1,5,7,1])
print(res)
assert res == 49

 [4, 2, 6, 2, 9, 4, 8, 1, 5, 7, 1]
     [4, 2, 6, 2, 9]
         [4, 2]
             [4]
         p= 4
             [2]
         q= 2
     p= 6
         [6, 2, 9]
             [6]
         p= 6
             [2, 9]
                 [2]
             p= 2
                 [9]
             q= 9
         q= 11
     q= 17
 p= 23
     [4, 8, 1, 5, 7, 1]
         [4, 8, 1]
             [4]
         p= 4
             [8, 1]
                 [8]
             p= 8
                 [1]
             q= 1
         q= 9
     p= 13
         [5, 7, 1]
             [5]
         p= 5
             [7, 1]
                 [7]
             p= 7
                 [1]
             q= 1
         q= 8
     q= 13
 q= 26
49

def cadillac(lst, level=0):
    raise Exception('TODO IMPLEMENT ME !')

res = cadillac([4,2,6,2,9,4,8,1,5,7,1])
print(res)
assert res == 49

 [4, 2, 6, 2, 9, 4, 8, 1, 5, 7, 1]
     [4, 2, 6, 2, 9]
         [4, 2]
             [4]
         p= 4
             [2]
         q= 2
     p= 6
         [6, 2, 9]
             [6]
         p= 6
             [2, 9]
                 [2]
             p= 2
                 [9]
             q= 9
         q= 11
     q= 17
 p= 23
     [4, 8, 1, 5, 7, 1]
         [4, 8, 1]
             [4]
         p= 4
             [8, 1]
                 [8]
             p= 8
                 [1]
             q= 1
         q= 9
     p= 13
         [5, 7, 1]
             [5]
         p= 5
             [7, 1]
                 [7]
             p= 7
                 [1]
             q= 1
         q= 8
     q= 13
 q= 26
49

b,c,d) Answers to remaining questions:

Show answer

ANSWER:

2. It returns the sum of all numbers in \(\Theta(n \log_2{n})\)

3. The answers to ask for termination are the following ones:

1. By repeatedly reducing input size, do we eventually end up in a branch with a return?

2. Are we reducing input size when calling cadillac?

Since the answer to both is yes, we can conclude the function will always terminate

4. Informal argument: we can picture the time spent in slice creation ad recursive calls like this:

                n                       recursion level
|-------------------------------|       1
|---------------|---------------|       2
|-------|-------|-------|-------|       3
|---|---|---|---|---|---|---|---|       .
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|       log_2(n)

Think of the internal vertical bars as the costs for calculating splitting points, placing recursive calls and summing the results obtained from calls from level below. The horizontal dashes represent the cost of copying cells when we slice.

It looks like a rectangle which is always fully traversed, thereafore to compute the complexity we can multiply the sides to get \(\Theta(n \log_2{n})\)

Formal argument (required during exam!):

We can apply the Master Theorem like so:

\(\normalsize a = 2\) (two calls)

\(\normalsize b = 2\) (input size is split in half at each call)

\(\normalsize c = 1\): recursive calls arguments are slices, which means a copy of the list is made prior to the call so we have a dependency on \(n\) (which wins over other rows with \(O(1)\) complexity)

\(\beta = 1\) (recursive operations depend linearly on input size)

to get:

\(\large T(n) = 2 T(n/2) + 1n^1\)

\(\large \alpha = \frac{log{a}} {log{b}} = \frac{\log{2}}{\log{2}} = 1\)

We are in the case \(\normalsize \alpha = \beta\) as \(\normalsize 1 = 1\), so we can confirm the estimation:

\(\large T(n) = \Theta(n^\alpha \log{n}) = \Theta(n^1 \log{n}) = \Theta(n\log{n})\)

Exercise - ducati

The following function is similar to the previous one, but doesn’t create slices

• lst : list of \(n\) integers

• i : left integer index included

• j : right integer index excluded

a). Does it behave the same?

b). What’s the time complexity? Try giving both an informal argument and a precise one through the Master Theorem

def ducati_rec(lst, i,j):
    interval =  j - i

    if interval == 0:
        return 0

    if interval == 1:
        return lst[i]

    k = i + (interval // 2)
    p = ducati_rec(lst,i,k)
    q = ducati_rec(lst,k,j)
    return p + q

def ducati(lst):
    return ducati_rec(lst,0,len(lst))

Show answer

ANSWER:

1. It’s still a sum of the elements, but executes faster, the complexity is \(\Theta(n)\)

2. Informal argument: notice this time we are not creating slices, we only calculate the splitting points \(log_2(n)\), times and only at the very end of recursion we extract \(n\) values from the list to sum them up, so splitting points are much sparser than the number of cells and we can see that visually represent the internal nodes of a full binary tree of height \(\log_2{n}\) which is always fully traversed, with the leaves being the single cells. Discrete math theory tells us are the number of internal nodes of a full binary is number the leaves minus 1, so roughly complexity should be \(O(n + n - 1) = O(n)\)

                n                       recursion level
|                               |       1
|               |               |       2
|       |       |       |       |       3
|   |   |   |   |   |   |   |   |       .
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|       log_2(n)

def ducati_rec(lst, i,j):
    interval =  j - i              # 1

    if interval == 0:              # 1
        return 0                   # 1

    if interval == 1:              # 1
        return lst[i]              # 1

    k = i + (interval // 2)        # 1
    p = ducati_rec(lst,i,k)        # recursive call: ?
    q = ducati_rec(lst,k,j)        # recursive call: ?
    return p + q                   # 1

def ducati(lst):                         # 1
    return ducati_rec(lst,0,len(lst))    # 1

Formal argument (required during exam!):

We can apply the Master Theorem like so:

\(\normalsize a = 2\) (two calls)

\(\normalsize b = 2\) (input size is split in half at each call)

\(\normalsize c = 7\)

\(\beta = 0\) (although we have some constant time operations, they don’t depend on input size)

to get:

\(\large T(n) = 2 T(n/2) + 7n^0\)

\(\large \alpha = \frac{log{a}} {log{b}} = \frac{\log{2}}{\log{2}} = 1\)

We are in the case \(\normalsize \alpha > \beta\) as \(\normalsize 1 > 0\), so we can confirm the estimation:

\(\large T(n) = \Theta(n^\beta) = \Theta(n^1) = \Theta(n)\)

Analysis - more exercises

Theory exercises (complexity, tree visits, graph visits) - by Alberto Montresor