(c) Consider the function definitions oumt and aum2 that calculates the summatio

Question

(c) Consider the function definitions oumt and aum2 that calculates the summation of all integer values in the range of I and n-1, as given in Figure Q3.1. int cuml (inc.n) int sum sum-n (n-3)/2 return aum int sum2 (int n) inti. aum-0: forti-1: in: i+) sum sum + i; return aum Figure Q3. i) State clearly the time complexity for each statement (if any) of functions suml and sum2, Calculate the worst-case time complexity of both functions 1612+2 marks ii) Estimate the Big-O of both functions 12+2 marks] ii) Based on your finding in part (ii), comment on the eficiency of both 12 marks] implementations in term of execution time.

Explanation / Answer

i)funciton1:

a)int sum;

This is one time executing line so the time compexity of this is O(1)

b)sum=n*(n-1)/2

we know that this is funtion (n^2-n)/2 th complexity of this id O(n^2)

function2:

a)int i,sum=0;

This is one time executing line so the time compexity of this is O(1)

b)for(i=1;i<n;i++)

sum=sum+i;

we know that this will run times so the complexity of this is O(n)

ii)

function1:

The Big-O of function1 is equal to O(1)+O(n^2)=O(n^2)

function2:

The Big-O of function2 is equal to O(1)+O(n)=O(n)

iii)

The function1 has more complexity than function2,In terms of execution time the

second function has more efficiency

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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