Find the complexity (big-O) of the following algorithms without computing the nu

Question

Find the complexity (big-O) of the following algorithms without computing the number of primitive operations.

Find the complexity (big-O) of the following algorithms without computing the number of primitive operat ions. for i 1 to m do end for for i 1 to n do for i 1 to n do sts+i end for for j 1 to n do b) s0 end for for i 1 to n do end for for j 1 to i do sstitj end for for i 1 to n do end for end for for i 1 to n do c)st_0 ifi is even then while i 21 do for j 1 to n do sts+i end for end while else end if end for Remark. In d you cannot reason that O(m)+O(n2) (n2), why not?

Explanation / Answer

a) It is of O(n) as loop is running for n times;

b) for i = 1 j = 0
       2     j = 1
       3      j = 2

       for i = n   j = n-1.
       Adding all that we get 1 + 2 + 3 + 4....+n-1 = (n-1)*n/2
       This is of O(n^2)

c) loop runs for n times. It is of O(n)

d) O(m) + O(n^2)

   We can not take this as just O(n^2) as there is no dependency on m and n.Though may be the dominating partner will be O(n^2)

e) n + (n/2 + n/2*n) (loop runs for i = even only.)

    This is of O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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