Give a big-Oh characterization, in terms of n, of the running time of the example4 function shown in Code Fragment 3.10.

Transcribed Image Text:

1 def example1(S): "Return the sum of the elements in sequence S.""" n = len(S) total = 0 2 3 4 for j in range(n): total += S[j] # loop from 0 to n-1 5 6. return total 9 def example2(S): "Return the sum of the elements with even index in sequence S.""" n = len(S) total = 0 for j in range(0, n, 2): total += S[j] 10 11 12 # note the increment of 2 13 14 15 return total 16 def example3(S): """ Return the sum of the prefix sums of sequence S."" n = len(S) 17 1111 18 19 total = 0 20 for j in range(n): for k in range(1+j): total += S[k] # loop from 0 to n-1 # loop from 0 to j 21 22 23 24 return total 25 26 def example4(S): """Return the sum of the prefix sums of sequence S.""" n = len(S) prefix = 0 total = 0 27 28 29 30 for j in range(n): prefix += S[j] total += prefix 31 32 33 return total 34 35 36 def example5(A, B): """Return the number of elements in B equal to the sum of prefix sums in A.' n = len(A) # assume that A and B have equal length 37 38 39 count = 0 for i in range(n): total = 0 # loop from 0 to n-1 40 41 for j in range(n): for k in range(1+j): total += A[k] if B[i) == total: count += 1 # loop from 0 to n-1 # loop from 0 to j 42 43 44 45 %3D3%3= 46 47 return count Code Fragment 3.10: Some sample algorithms for analysis.