Give a big-Oh characterization, in terms of n, of the running time of the exampl
ID: 3666692 • Letter: G
Question
Give a big-Oh characterization, in terms of n, of the running time of the example1-example5 function shown in Code Fragment.(Give simple analysis)
def example1(S):
”””Return the sum of the elements in sequence S.””” n = len(S)
total = 0
for j in range(n):
total += S[j] return total
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] return total
def example3(S):
”””Return the sum of the prefix sums of sequence S.””” n = len(S)
total = 0
for j in range(n):
for k in range(1+j): total += S[k]
return total
def example4(S):
”””Return the sum of the prefix sums of sequence S.””” n = len(S)
prefix = 0
total = 0
for j in range(n):
prefix += S[j]
total += prefix return total
def example5(A, B):
”””Return the number of elements in B equal to the sum of prefix sums in A.””” n = len(A)
count = 0
for i in range(n):
total = 0
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
# loop from 0 to n-1
# note the increment of 2
# loop from 0 to n-1 # loop from 0 to j
# assume that A and B have equal length
# loop from 0 to n-1
return count
Explanation / Answer
Multiple Questions : Answering 1st 3 questions.
-----------------------------------------------------------------------------------------
def example1(S):
”””Return the sum of the elements in sequence S.”””
n = len(S)
total = 0
for j in range(n):
total += S[j]
return total
Here the for loop will run from 0 – n-1 and hence a total of n times. Thus the running time of this algorithm is O(n) .
-----------------------------------------------------------------------------------------
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]
return total
Here the for loop will run from 0 – n-1 for alternate elements like 0 , 2, …., n-1 and hence a total of n/2 times. Thus the running time of this algorithm is O(n/2) = O(n) .
-----------------------------------------------------------------------------------------
def example3(S):
”””Return the sum of the prefix sums of sequence S.”””
n = len(S)
total = 0
for j in range(n):
for k in range(1+j):
total += S[k]
return total
Here the outer for loop will run from 0 – n-1 and the inner for loop will run from 1 – n for each values of j = 0 to j = n-1 .
Thus the running time of this algorithm is 1 + 2 + 3 + …. + n-1 + n = n*( n+1) /2=( n2 + n )/2
O((n2 + n)/2) = O(n2) .
---------------------------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.