Question 1:120 points] For each of the tollowing tour program tragments, give an

Question

Question 1:120 points] For each of the tollowing tour program tragments, give an analysis of the running time in terms of Big-O. Your answer will be a very short statement T(n) = 0(?) Your algorithm run time analysis should only contain the highest term when writing in terms of Big O. For example: TON)-O(n'+5n') would be incorrect, it should be simplified (dropping the lowest terms) and written as: T(N)-O(n') TN)-? Sum-e; for i = 1 to N do sum = sum + i; T(N)? b) Sume for i 1 to N do for j-1 to N do for k- 1 to N do Sum Sum1; TN)-? (c) Sum - e for i-1 to N do for j-1 to N do SumSum1

Explanation / Answer

Following are the time-complexities for the above fragments:

(a) T(N) = O(n)

(b) T(N) = O(n3)

(c) T(N) = O(n3)

(d) T(N) = O(n4)

(c)

Sum = 0

for i=1 to N2 do => outer for loop runs O(n2) times

for j = 1 to N do => inner for loop runs O(n) times

Sum = Sum + 1

Overall : O(n2 * n) = O(n3)

(d)

Sum = 0

for (i=0; i<n; ++i) => for loop runs O(n) times

for (j=0; j< i*i; ++j) => for loop runs O(n2) times

for(k=0; k < j; ++k) => for loop runs O(n) times

++Sum

Overall : O(n * n2 * n) = O(n4)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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