MIT assignment

Question

Find the complexity of the following code fragment:

int i = 1;
for(; i <= n logn; i++)
{
 for(i++; i <= n; i++)
 {
   printf("1")
 }
}

Comments

T (n)=nlogn + n^2logn+c

So complexity should be n^2 login don't you think.

---

That sure would have been the case if we were to use 2 different enumerators for the two for loops. Since we're using same enumerator, leading to a certain relation between the loops, (ie The inner loop is rendered ineffective) giving O(nlogn) time complexity.

---

Thanks got the point.

I have one query I am facing problem in solving dma questions in coa can you suggest something where I can able to understand the concept.

Answer 1

The time complexity is going to be O(nlogn)

The inner loop is running for only O(n) times, and once the value of i become n+1 it fails the condition and the inner loop will halt and will not  going to run again. Now when it comes to the termination of the outer loop , it will terminate when the condition i<=nlogn become false, which will happen only when i=nlogn+1, and the will happen after nlogn steps.

Comments

WHY IT IS NOT (nnlogn)

because the outer loop will run for n*log times and the inner loop will run for n times

---

for i = 1 from outer loop , inner loop will run n times,

then for outer loop i starts from n+1 and runs till n logn times

hence, 1......n will be run by inner loop only once

            n+1........nlogn times outer loop will run

so T(n) = nlogn