Efficiency Practice

  1. Big-O Analysis: Problems and Solutions
    Find the Big-O runtime of the given function by computing the runtime of each line.

    The solutions are below, but try your best to solve it yourself before looking at the solutions.

    Problems
    Mild
    Problem 1 
    def foo(L): #L is a list
    i = 1
    listLength = len(L)
    result = [] 
    while i < listLength:
        result += L[i] 
        i *= 3 
    return i
    Problem 2 
    def foo(S): #S is a string
    stringLength = len(S) 
    i = stringLength
    result = {} 
    while i > 0: 
        result.add(S[i]) 
        i //= 3 
    return result
    Problem 3 
    def foo(L): # L is a list
    lenList = len(L) 
    count = 0 
    for i in range(lenList): 
        for j in range(lenList): 
            count += L[i] 
    return count
    Medium
    Problem 4 
    def foo(s): #s is a string of length N
    result = 0 
    for char in string.ascii_lowercase:
        if char in s:
            s = s[1:] 
            result += 1
    return result
    Problem 5 
    def foo(s):
    return len(s)
    Problem 6 
    def foo(L): #L is a list
    n = len(L) 
    for i in range(n**2, n**3, n):
        L.append(i) 
    for j in range(n//5, n//2, n//10):
        L.pop()
    return L
    Spicy
    Problem 7 
    def foo(L):
    result = [] 
    for i in range(1, len(sorted(L)) + 1):
        newList = len(L) * [i] 
        result.extend(newList)
    return sorted(result)
    Problem 8 
    def foo(L): # L is a square, 2D list
    n = len(L)
    j = 1 
    count = 0
    while j < n: 
        for i in range(n): 
            if max(L[j]) in L[i]: 
                count += 1
        j *= 2 
    return count
    Problem 9 
    def bigOh(L):
    new = list()  
    for i in range(len(L)):
        new.extend(L[:i:2])
    new.sort()
    result = set(new) 
    return result

    Solutions
    Mild
    Problem 1 
    def foo(L): #L is a list
    i = 1 # O(1)
    listLength = len(L) # O(1)
    result = [] # O(1)
    while i < listLength: # O(log(N))
        result += L[i] # O(1)
        i *= 3 # O(1)
    return i # O(1)
# Overall -- O(log(N))
    Problem 2 
    def foo(S): #S is a string
    stringLength = len(S) # O(1)
    i = stringLength # O(1)
    result = {} # O(1)
    while i > 0: # O(log(N))
        result.add(S[i]) # O(1)
        i //= 3 # O(1)
    return result # O(1)
# Overall -- O(log(N))
    Problem 3 
    def foo(L): # L is a list
    lenList = len(L) # O(1)
    count = 0 # O(1)
    for i in range(lenList): # O(N)
        for j in range(lenList): # O(N)
            count += L[i] # O(1)
    return count # O(1)
# Overall -- O(N ** 2)
    Medium
    Problem 4 
    def foo(s): #s is a string of length N
    result = 0 #O(1)
    for char in string.ascii_lowercase: #O(1)
        if char in s: #O(N)
            s = s[1:] #O(N)
            result += 1 #O(1)
    return result #O(1)
#Overall - #O(N)
    Problem 5 
    def foo(s):
    return len(s) # O(1)
# Overall O(1)
    Problem 6 
    def foo(L): #L is a list
    n = len(L) #O(1)
    for i in range(n**2, n**3, n): #O(n**2)
        L.append(i) #O(1)
    for j in range(n//5, n//2, n//10): #O(1)
        L.pop() #O(1)
    return L #O(1)
#Overall: O(n**2)
    Spicy
    Problem 7 
    def foo(L):
    result = [] # O(1)
    # initial computation of O(nlogn), then runs O(n) times
    for i in range(1, len(sorted(L)) + 1): # O(nlogn) + n iterations 
        newList = len(L) * [i] # O(n)
        result.extend(newList) # O(n)
    # result has length O(n**2)
    return sorted(result) # n**2 log(n**2)
# Overall O(n**2 log(n))
    Problem 8 
    def foo(L): # L is a square, 2D list
    n = len(L) #O(1)
    j = 1 #O(1)
    count = 0 #O(1)
    while j < n: #O(logn)
        for i in range(n): #O(n)
            if max(L[j]) in L[i]: #O(n) 
                count += 1 #O(1)
        j *= 2 #O(1)
    return count #O(1)
#Overall: O(n**2logn)
    Problem 9 
    def bigOh(L):
    new = list()            # O(1)
    for i in range(len(L)): # n times
        new.extend(L[:i:2])     # O(i) = O(n)
    new.sort()              # O(n^2 log(n))
    result = set(new)       # O(n^2)
    return result           # O(1)
# O(n^2 log(n))

  2. mostCommonName(L) in O(n) time
    Write the function mostCommonName, that takes a list of names (such as ["Jane", "Aaron", "Cindy", "Aaron"], and returns the most common name in this list (in this case, "Aaron"). If there is more than one such name, return a set of the most common names. So mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) returns the set {"Aaron", "Jane"}. If the set is empty, return None. Also, treat names case sensitively, so "Jane" and "JANE" are different names. You should write three different versions, one that runs in O(n**2), O(nlogn) and O(n).
    def mostCommonName(L): return 42 # place your answer here! def testMostCommonName(): print("Testing mostCommonName()...", end="") assert(mostCommonName(["Jane", "Aaron", "Cindy", "Aaron"]) == "Aaron") assert(mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) == {"Aaron", "Jane"}) assert(mostCommonName(["Cindy"]) == "Cindy") assert(mostCommonName(["Jane", "Aaron", "Cindy"]) == {"Aaron", "Cindy", "Jane"}) assert(mostCommonName([]) == None) print("Passed!") testMostCommonName()

  3. getPairSum(a, target) in O(n) time
    Write the function getPairSum(a, target) that takes a list of numbers and a target value (also a number), and if there is a pair of numbers in the given list that add up to the given target number, returns that pair, and otherwise returns an empty list. If there is more than one valid pair, you can return any of them. You should write two different versions, one that runs in O(n**2) and the other in O(n). For example: 
    getPairSum([1],1) == []
getPairSum([5,2],7) in [ [5,2], [2,5] ]
getPairSum([10,-1,1,-8,3,1], 2) in [ [10,-8], [-8,10] ] (can also return [-1,3] or [1,1])
getPairSum([10,-1,1,-8,3,1],10) == []
    def getPairSum(a, target): return 42 # place your answer here! def testGetPairSum(): print("Testing getPairSum...", end="") assert(getPairSum([1],1) == []) assert(getPairSum([5, 2], 7) in [ [5, 2], [2, 5] ]) # (can return [10, -8] or [-1,3] or [1,1]) assert(getPairSum([10,-1,1,-8,3,1], 2) in [[10, -8], [-8, 10], [-1, 3], [3, -1], [1, 1]]) assert(getPairSum([10,-1,1,-8,3,1], 10) == []) assert(getPairSum([1, 4, 3], 2) == []) print("Passed!") testGetPairSum()

  4. mergeSortWithOneAuxList(a)
    Write the function mergeSortWithOneAuxList(a) that works just like mergeSort from the notes, only here you can only create a single aux list just one time, rather than once for each call to merge. To do this, you will need to create the aux list in the outer function (mergeSortWithOneAuxList) and then pass it as a parameter into the merge function. The rest is left to you. In a comment at the top of this function, include some timing measurements comparing this function to the original mergeSort, and a brief reflection on whether or not this change was worthwhile.