139 views

### int i = 1; for(; i <= n logn; i + +) {

for(i + +; i <= n; i + +)
{
print(1)
}

}

| 139 views
0
It should be O(nlogn).
0
its coming O(nlogn) for me.
+1
Yes, Exactly.
0
T (n)=nlogn + n^2logn+c

So complexity should be n^2 login don't you think.
0
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.
0
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.

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.
by Active (1.2k points)
selected by
0
WHY IT IS NOT (nnlogn)

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

### 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

+1 vote