Algorithm analysis and recursion

Download exercises zip

Browse files online

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:

• Luca Bianco’s Introduction to algorithms slides

• Luca Bianco’s Algorithms and complexity slides

• 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]])  #  x[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(len(1,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.

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:

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.

Operation	Big-O Efficiency	Operation	Big-O Efficiency
copy	\(O(n)\)	in operator	\(O(1)\)
get item	\(O(1)\)	set item	\(O(1)\)
delete item	\(O(1)\)	iteration	\(O(n)\)

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

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

Recursion - exercises

Exercise - gap_rec

✪✪ In a list \(L\) containing \(n≥2\) integers, a gap is an index \(i\), \(0< i < n\), such that \(L[i−1]< L[i]\)

If \(n≥2\) and \(L[0]< L[n−1]\), \(L\) contains at least one gap

Design an algorithm that, given a list \(L\) containing \(n≥2\) integers such that \(L[0]< L[n−1]\), finds a gap in the list.

We wrote here the gap function as pseudocode, try coding it in Python:

Use the following skeleton and add some test. To understand what’s going on, try copy-pasting in Python tutor

Notice that

• We created a function gap_rec to differentiate it from the iterative one

• Users of gap_rec function might want to call it by passing just a list, in order to find any gap in the whole list. So for convenience the new function gap_rec(L) only accepts a list, without indexes i and j. This function just calls the other function gap_rec_helper that will actually contain the recursive calls. So your task is to translate the pseudocode of gap into the Python code of gap_rec_helper, which takes as input the array and the indexes as gap does. Adding a helper function is a frequent pattern you can find when programming recursive functions.

CAREFUL ABOUT gap_rec ASSUMPTIONS!

The specification of gap_rec assumes the input is always a list of at least two elements, and that the first element is less or equal than the last one. If these conditions are not met, function behaviour could be completely erroneus!

When preconditions are not met, execution could stop because of an error like index out of bounds, or, even worse, we might get back some wrong index as a gap! To prevent misuse of the function, a good idea can be putting a check at the beginning of the gap_rec function. Such check should immediately stop the execution and raise an error if the parameters don’t satisfy the preconditions. One way to do this could be to to some assertion like this:

def gap_rec(L, i , j):
    assert len(L) >= 2
    assert L[0] <= L[len(L)-1]

• These commands will make python interrupt execution and throw an error as soon it detects list L is too small or with wrong values

• This kind of behaviour is also called fail fast, which is better than returning wrong values!

• You can put any condition you want after assert, but ideally they should be fast to execute.

• asserts might be better here than raise Exception constructs because asserts can be disabled with a flag passed to the interpreter. So, when you debug you can take advantage of them, and when the code is production quality and supposed to be bug free you can disable all assertions at once to gain in execution speed.

GOOD PRACTICE: Notice we wrote what the helper function is expected to receive as a comment. Writing down specs often helps understanding what the function is supposed to do, and helps users of your code as well!

VII COMMANDMENT: You shall also write on paper!

To get an idea of how gap_rec is working, draw histograms on paper like the following, with different heights at index m:

Notice how at each recursive call, we end up with a histogram that is similar to the inital one, that is, it respects the same preconditions (a list of size >= 2 where first element is smaller or equal than the last one)

Show solution

def gap_rec(L, i, j):

    if j == i+1:
        return j
    else:
        m = (i+j) // 2
        if L[m] < L[j]:
            return gaprec(L,m,j)
        else:
            return gaprec(L,i,m)


def gap(L):

    return gap_rec(L, 0, len(L) - 1)


# try also to write asserts

def gap_rec(L, i, j):
    raise Exception('TODO IMPLEMENT ME !')

def gap(L):
    raise Exception('TODO IMPLEMENT ME !')

# try also to write asserts

Exercise - yamaha

What does this function do? What’s the time complexity?

• 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: It sums all the numbers in \(O(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).

Exercise - mul2

Write a recursive function mul_rec which given a list RETURN a NEW list with all elements multiplied by two.

ONLY USE .append() to build output list: in order to use it, you will need the parameter acc, which is a list into which you will accumulate the elements found during the recursion. At the end of recursion you will return acc

MUST execute in \(O(n)\)

DO NOT use for, while cycles nor list comprehensions

DO NOT use slices

DO NOT use in operator, .find nor .index methods

DO NOT use .extend method nor + operator - they’re expensive !

Show solution

def mul2_rec(lst, acc):

    if len(acc) == len(lst):
        return acc
    else:
        i = len(acc)
        acc.append(lst[i] * 2)
        return mul2_rec(lst, acc)


def mul2(lst):
    return mul2_rec(lst, [])

assert(mul2([])) == []
assert(mul2([3])) == [6]
assert(mul2([5,8])) == [10,16]

nums = [4,6,2,7,3]
assert(mul2(nums)) == [8,12,4,14,6]
assert nums == [4,6,2,7,3]

def mul2_rec(lst, acc):
    raise Exception('TODO IMPLEMENT ME !')

def mul2(lst):
    return mul2_rec(lst, [])

assert(mul2([])) == []
assert(mul2([3])) == [6]
assert(mul2([5,8])) == [10,16]

nums = [4,6,2,7,3]
assert(mul2(nums)) == [8,12,4,14,6]
assert nums == [4,6,2,7,3]

Exercise - search_rec

Write a recursive function which RETURN True if el is in the first i elements of lst and False otherwise

• lst is a list of \(n\) elements

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

DO NOT use in operator, .find nor .index methods

DO NOT use for, while cycles nor list comprehensions

DO NOT use slices

MUST execute in \(O(n)\)

Show solution

def search_rec(el, lst, i):

    if i <= 0:
        return False
    else:
        if el == lst[i-1]:
            return True
        else:
            return search_rec(el, lst, i - 1)


def search(el, lst):
    return find_rec(el, lst, len(lst))

assert search_rec(6, [], 0) == False
assert search_rec(5, [5], 0) == False
assert search_rec(5, [5], 1) == True
assert search_rec(2, [2,9], 0) == False
assert search_rec(2, [2,9], 1) == True
assert search_rec(2, [2,9], 2) == True
assert search_rec(5, [9,5], 2) == True
assert search_rec('c', [5,'r',6,'c'], 4) == True
assert search_rec(2, [4,'z',8,3,2], 5) == True
assert search_rec(7, [4,9,8,'x',2], 5) == False

def search_rec(el, lst, i):
    raise Exception('TODO IMPLEMENT ME !')

def search(el, lst):
    return find_rec(el, lst, len(lst))

assert search_rec(6, [], 0) == False
assert search_rec(5, [5], 0) == False
assert search_rec(5, [5], 1) == True
assert search_rec(2, [2,9], 0) == False
assert search_rec(2, [2,9], 1) == True
assert search_rec(2, [2,9], 2) == True
assert search_rec(5, [9,5], 2) == True
assert search_rec('c', [5,'r',6,'c'], 4) == True
assert search_rec(2, [4,'z',8,3,2], 5) == True
assert search_rec(7, [4,9,8,'x',2], 5) == False

Exercise - bin_search

If the list is already sorted we can write a faster search: write a recursive function which RETURN True if el is in the subsequence [i,j) of lst, and False otherwise

• lst is a list of \(n\) already sorted elements

• i and j are indeces between 0 included and \(n\) included

MUST execute in \(O(log(n))\): to obtain this complexity, you will need to keep splitting the search interval in halves until you have a 1 element interval (or empty interval)

DO NOT use in operator, .find nor .index methods

DO NOT use for, while cycles nor list comprehensions

DO NOT use slices

Show solution

def bin_search_rec(el, lst, i, j):

    #print('i =', i, ' j =', j)

    interval = j - i
    #print('interval =', interval)
    k = (i + j) // 2
    #print('k =', k)

    if interval <= 0:
        return False
    elif el == lst[k]:
        return True
    #elif interval == 1:
    #    return False
    elif el > lst[k]:
        return bin_search_rec(el, lst, k+1, j)
    else:
        return bin_search_rec(el, lst, 0, k)


def bin_search(el, lst):
    return bin_search_rec(el, lst, 0, len(lst))


print(bin_search(33, [8,9,15,17,20,24,28,29,33,36,39]))

assert bin_search(5, [5]) == True
assert bin_search(4, []) == False
assert bin_search(3, [7]) == False
assert bin_search(3, [3,7]) == True
assert bin_search(3, [3,6]) == True
assert bin_search(4, [2,9]) == False
assert bin_search(5, [2,9]) == False
assert bin_search(5, [5,7,9]) == True
assert bin_search(7, [5,7,9]) == True
assert bin_search(9, [5,7,9]) == True
assert bin_search(4, [5,7,9]) == False
assert bin_search(6, [5,7,9]) == False
assert bin_search(8, [5,7,9]) == False
assert bin_search(10, [5,7,9]) == False
assert bin_search(33, [8,9,15,17,20,24,28,29,33,36,39]) == True
assert bin_search(10, [8,9,15,17,20,24,28,29,33,36,39]) == False

True

def bin_search_rec(el, lst, i, j):
    raise Exception('TODO IMPLEMENT ME !')

def bin_search(el, lst):
    return bin_search_rec(el, lst, 0, len(lst))


print(bin_search(33, [8,9,15,17,20,24,28,29,33,36,39]))

assert bin_search(5, [5]) == True
assert bin_search(4, []) == False
assert bin_search(3, [7]) == False
assert bin_search(3, [3,7]) == True
assert bin_search(3, [3,6]) == True
assert bin_search(4, [2,9]) == False
assert bin_search(5, [2,9]) == False
assert bin_search(5, [5,7,9]) == True
assert bin_search(7, [5,7,9]) == True
assert bin_search(9, [5,7,9]) == True
assert bin_search(4, [5,7,9]) == False
assert bin_search(6, [5,7,9]) == False
assert bin_search(8, [5,7,9]) == False
assert bin_search(10, [5,7,9]) == False
assert bin_search(33, [8,9,15,17,20,24,28,29,33,36,39]) == True
assert bin_search(10, [8,9,15,17,20,24,28,29,33,36,39]) == False

True

Exercise - rev

Write a recursive function rev which given a list and an index i, RETURN a NEW sublist with the elements starting from i included in reverse order.

• lst is a list of \(n\) integers

• i is an index between 0 included and \(n\) included

>>> rev(['a','b','c','d','e'], i=0)
['e', 'd', 'c', 'b', 'a']
>>> rev(['a','b','c','d','e'], i=2)
['e', 'd', 'c']

ONLY USE .append() to build return list

MUST execute in \(O(n)\)

DO NOT use for, while cycles nor list comprehensions

DO NOT use .reverse() nor reversed()

DO NOT use slices

DO NOT use .extend method nor + operator - they’re expensive !

DO NOT use in operator, .find nor .index methods

Show solution

def rev(lst, i=0):

    if i == len(lst):
        return []
    else:
        ret = rev(lst, i + 1)
        ret.append(lst[i])
        return ret


assert(rev([])) == []
assert(rev(['z'])) == ['z']
assert(rev(['a','z'])) == ['z','a']

chars = ['a','b','c','d','e']
assert(rev(chars)) == ['e', 'd', 'c', 'b', 'a']
assert chars == ['a','b','c','d','e']

def rev(lst, i=0):
    raise Exception('TODO IMPLEMENT ME !')

assert(rev([])) == []
assert(rev(['z'])) == ['z']
assert(rev(['a','z'])) == ['z','a']

chars = ['a','b','c','d','e']
assert(rev(chars)) == ['e', 'd', 'c', 'b', 'a']
assert chars == ['a','b','c','d','e']

Exercise - unnest

Write a recursive function unnest_rec which takes a list with an element and a nested list, and outputs a NEW list with all the nested elements in sequence.

DO NOT use for nor while cycles or list comprehensions

DO NOT use slices

MUST execute in \(O(n)\)

NOTE 1: if you use the + operator or .extend methods, you will likely get a \(O(n^2)\) complexity (remember + takes \(O(n)\) and .extend \(O(m)\)).

.append would be much faster, but to do so you need the parameter acc, which is a list into which you will accumulate the elements found during the recursion. At the end of recursion you will return acc

NOTE 2: last list contains only one element

Show solution

def unnest_rec(lst, acc):

    if len(lst) == 0:
        return []
    acc.append(lst[0])
    if len(lst) == 1:
        return acc
    else:
        return unnest_rec(lst[1], acc)


def unnest(lst):
    return unnest_rec(lst, [])

print(unnest(['a',['b',['c']]]))

assert unnest([]) == []
assert unnest(['a']) == ['a']
assert unnest(['a',['b']]) == ['a', 'b']
assert unnest(['a',['b',['c']]]) == ['a','b','c']
assert unnest(['z',['q',['r']]]) == ['z','q','r']
assert unnest(['a',['b',['c',['d',['e']]]]]) == ['a','b','c','d','e']

['a', 'b', 'c']

def unnest_rec(lst, acc):
    raise Exception('TODO IMPLEMENT ME !')

def unnest(lst):
    return unnest_rec(lst, [])

print(unnest(['a',['b',['c']]]))

assert unnest([]) == []
assert unnest(['a']) == ['a']
assert unnest(['a',['b']]) == ['a', 'b']
assert unnest(['a',['b',['c']]]) == ['a','b','c']
assert unnest(['z',['q',['r']]]) == ['z','q','r']
assert unnest(['a',['b',['c',['d',['e']]]]]) == ['a','b','c','d','e']

['a', 'b', 'c']

Exercise - cadillac

Look at the following code:

1. Is recursion eventually terminating after some time?

2. What’s the time complexity?

3. What is this function doing?

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

• 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

Show answer

ANSWER: It returns the sum of all numbers in \(O(n \log_2{n})\)

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 bars as the costs for calculating splitting points, placing recursive calls and summing the results obtained from calls from level below.

It looks like a rectangle, thereafore to compute the complexity we can multiply the sides to get \(O(n \log_2{n})\)

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

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

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

1. Does it behave the same?

2. What’s the time complexity?

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: It’s still a sum of the elements, but executes faster, the complexity is \(O(\log{n} + n) = O(n)\)

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 cost is the maximum between the two: \(O(\log{n} + n) = O(n)\)

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

def ducati_rec(lst, i,j):
    #jupman-raise
    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)        # 1
    return p + q                   # 1
    #/jupman-raise

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

Analysis - more exercises

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

Recursion - more exercises

Computer Science Circles: nice chapter about recursion with some exercises

W3 Resources: some recursion exercises

Edabit: Search by setting ‘Recursion’ as tag - notice many provided solutions are not actually in recursive format.

Geeks for geeks (Pyhton solutions are typically provided down in the pages):

• questions set 2

• questions set 3

• questions set 4

• questions set 5

• questions 6

• questions 7

• Length of a string

• Recursive programs to find min and max

• Print a pattern without using any loop

• Sum triangle from array

• Print all n-digit strictly increasing numbers

• Recursive insertion sort