6. For each of the following four program fragments, give an analysis of the run

Question

6. For each of the following four program fragments, give an analysis of
the running time. Give this time in Big-O notation using function
with the least order of magnitude. Basically don't say the complexity
is O(N9) if it is also O(N2)

(a) Sum = 0;
       for i = 1 to N do
            Sum = Sum +i;

(b) Sum = 0;
        for i = 1 to N do
             for j = 1 to N do
                  for k = 1 to N do
                       Sum = Sum + 1;

(c) Sum = 0;
          for i = 1 to N2 do
                for j = 1 to N do
                  Sum = Sum + 1;

Explanation / Answer

a) O(N)

b) O(N^3)

c) O(N * N2)

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

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