Give a big-O estimate for the number of operations (where an operation is an add

Question

Give a big-O estimate for the number of operations (where an operation is an addition or a multiplication) used in this segment of an algorithm. t:= 0 for i:= 1 to 3 for j: = 1 to 4 t: = t + ij (e) Give a big-O estimate for the number additions used in this segment of an algorithm. t: = 0 for i:= 1 to n for j: = 1 to n t: = t + i + j (f) What is the largest n for which one can solve within one second a problem using an algorithm that requires f(n) bit operations, where each bit operation is carried out in 1nano-second, with these functions f(n)? Assume base-2 for log. (i) log n (ii) n (iii) n^2 (vi) 2^n

Explanation / Answer

(d)

t:=0 -> One assignment operation

for i:= 1 to 3 -> Every loop iteration one assignment and one addition. This happens 3 times.

for j:= 1 to 4 -> Every loop iteration one assignment and one addition. This happens 12 times.

t := t+ij -> One assignment and one addition. This happens 12 times.

So the total operations are 12+12+3+1 = 28.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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