3.1) a. sum = 0; for (int i = 0; i < n; i++) sum++; b. sum = 0; for (int i = 0;

Question

3.1)

a.    sum = 0;

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

sum++;

b.    sum = 0;

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

for (int j = 0; j < n; j++)

sum++;

c.    sum = 0;

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

for (int j = 0; j < n * n; j++)

sum++;

d.    sum = 0;

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

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

sum++;

e.   sum 0;

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

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

for (int k = 0; k < j; k++)

sum++;

Implement loops a -f in Problem 3.1 and show heuristically that runtime grows according to Big-O for each set of loops.

Explanation / Answer

Answer:

a) The big O complexity of this piece of code is O(n) . Since it has only one for loop running till n.

b) Big O complexity of this algorithm is O(n^2) . Two for loops , one running till n and second runnig till n also , so total = O(n) * O(n) = O(n^2).

c) Big O complexity is O(n^3) . One loop running till n and other running till n^2 . Total = O(n) * O(n^2) = O(n^3).

d) Big O complexity is O(n^2) . One loop runnig till n and other till i which itself running till n. So , total = O(n) * O(n) = O(n^2).

e) Big O complexity = O(n^5) . One loop runnig till n ,second loop runnig till i*i = n*n = n^2

third loop till j , j itself running till n^2 . Total = O(n) * O(n^2) * O(n^2) = O(n^5)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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