### Chapter 3 algorithm analysis of source code in the book

3-1 function to return the maximum value of Python list

""" //Function that returns the maximum value of Python list """ def find_max(data): """ Return the maximum element from a nonempty Python list. :param data: :return: """ biggest = data[0] # The initial value to beat for val in data: # For each value: if val > biggest: # if it is greater than the best so far. biggest = val return biggest # When loop ends. biggest is the max.

The time complexity is O(n)O(n)O(n).

If based on random sequence, the expected number of times the maximum value of the algorithm is updated is O (log n) O (log n) O (log n)

3-2 prefix average

""" //Prefix average, algorithm prefix_average1 """ import time def prefix_average1(S): """ Return list such that, for all j, A[j] equals average of S[0],...,S[j] :param S: :return: """ n = len(S) A = [0] * n # create new list of n zeros for j in range(n): total = 0 for i in range(j + 1): total += S[i] A[j] = total / (j + 1) return A if __name__ == '__main__': data = [x for x in range(10000)] print(data) curr = time.time() prefix_data = prefix_average1(data) print(time.time() - curr) print(prefix_data)

The time complexity is O(n2)O(n^{2})O(n2), and the running time is 2.5133016109466553 seconds.

3-3 prefix average

""" //Prefix average, algorithm prefix_average2 """ import time def prefix_average2(S): """ Return list such that, for all j, A[j] equals average of S[0],...S[j]. :param S: :return: """ n = len(S) A = [0] * n # create new list of n zeros for j in range(n): A[j] = sum(S[0: j+1]) / (j + 1) # record the average return A if __name__ == '__main__': data = [x for x in range(10000)] print(data) curr = time.time() prefix_data = prefix_average2(data) print(time.time() - curr) print(prefix_data)

The time complexity is O(n2)O(n^{2})O(n2), and the running time is 0.4189138412475586 seconds.

3-4 prefix average

""" //Prefix average, algorithm prefix_average3 """ import time def prefix_average3(S): """ Return list such that, for all j, A[j] equals average of S[0],...S[j]. :param S: :return: """ n = len(S) A = [0] * n # create new list of n zeros total = 0 # compute prefix sum as S[0] + S[1],... for j in range(n): total += S[j] # update prefix sum to include S[j] A[j] = total / (j + 1) # compute average based on current sum return A if __name__ == '__main__': data = [x for x in range(10000)] print(data) curr = time.time() prefix_data = prefix_average3(data) print(time.time() - curr) print(prefix_data)

The time complexity is O(n)O(n)O(n), and the running time is 0.001027822494506836 seconds.

3-5 three sets do not intersect, algorithm disjoint1 tests three sets do not intersect

def disjoint1(A, B, C): """ Return True if there is no element common to all three lists. :param A: :param B: :param C: :return: """ for a in A: for b in B: for c in C: if a == b == c: return False # we found a common value return True # if we reach this, sets are disjoint

The time complexity is O(n3)O(n^{3})O(n3)

3-6 three sets do not intersect, algorithm disjoint1 tests three sets do not intersect

def disjoint(A, B, C): """ Return True if there is no element common to all three lists. :param A: :param B: :param C: :return: """ for a in A: for b in B: if a == b: # only check C if we found match from A and B for c in C: if a == c: # (and thus a == b == c) return False # we found a common value return True # if we reach this, sets are disjoint.

The time complexity is O(n2)O(n^{2})O(n2)