Give a big-Oh characterization, in terms of n, of the running time of the exampl

Question

Give a big-Oh characterization, in terms of n, of the running time of the example4 and example 5 functions shown below:

Write the individual time it takes to execute every statement on every line.

for ex:

1: n=len(S) exectutes in O(1) time.

2: A=[0]*n executes in O(n) time.

3: def example4(S) takes ____ time

4: prefix = 0 takes ____ time.

Do this for all statements of all the functions.

26 def example4(S) 27"" Return the sum of the prefix sums of sequence S.""" 28 n len(S) 29 prefix 0 30 total 0 31 for j in range(n): prefix += S total +- prefix 34 return total 35 36 def example5(A, B) 37"" Return the number of elements in B equal to the sum of prefix sums in A.""" 38 n=len(A) 39 count 0 40 for i in range(n): # assume that A and B have equal length # loop from 0 to n-1 total 0 for j in range(n): 42 43 # loop from 0 to n-1 # loop from 0 to J for k in range(1+j): total Alk] 45 46 if B[i]== total: count + 1 47 return count

Explanation / Answer

Ans.

def example4(S) takes O(n) time.

1. n = len(s) , exectutes in O(1) time.

2. prefix = 0 , exectutes in O(1) time.

3. total = 0 , exectutes in O(1) time.

4. for j in range (n) , exectutes in O(n) time. As loop runs n times.

5. prefix += S[j], exectutes in O(1) time.

6. total += prefix, exectutes in O(1) time.

7. return total, exectutes in O(1) time.

def example5(A,B) takes O(n3) time.

1. n = len(A) , statement exectutes in O(1) time.

2. count = 0 , statement exectutes in O(1) time.

3. for i in range (n) ,statement exectutes in O(n) time. // total time for the for loop is , n*n*n = O(n3)

4. total = 0, statement exectutes in O(1) time.

5. for j in range (n) , statement exectutes in O(n) time. // total time for the for loop is , n*(n+1) / 2 = O(n2)

6. for k in range (1+j) , statement exectutes in O((n+1) / 2) time. // total time for the for loop = O(n).

7. total += A[j], statement exectutes in O(1) time.

8. if B[i] == total, statement exectutes in O(1) time.

9. count += 1 , statement exectutes in O(1) time.

10. return count, statement exectutes in O(1) time.

Example for line 5,6 of def example5(A,B).

for( i = 0; i < n; i++)

for( j = 0; j < i; j++)

total = total + 2;

The running time for the operation total = total + 2; is a O(1) time.

OuterLoop i will executes n times. Now for inner j loop: For i = 1, it runs 1 times; i = 2, it runs 2 times; i = 3, it runs 3 times etc. Therefore it gets executed:

1 + 2 + ... + (n-1) + n = n(n+1) / 2, => (n+1) / 2 on average.

Thus the total running time would be O(n*(n+1)/2)* O(1) = O(n*n) = O(n2)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.