# MIT assignment

229 views

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

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

}

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.

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

## Related questions

1 vote
1
236 views
Find the complexity of the following function when called with some integer n: void foo(n) { int i,j,k,x=0; for (i=1 ; i ≤ n ; i++) for (j=1 ; j ≤ i * i ; j++) { for ( k = 1 ; k ≤ j ; k++) { x=x+10; } }
Arrange the following functions in their increasing order of complexities. $f(n) = n ^{0.999999} * logn$ ($log n$ is not in power) $g(n) = 10000 n$ $h(n) = n^{2}$ $k(n) = (1.000001)^{n}$ $p(n) =\large \frac{2 ^{√n}}{ n^{2}}$ $q(n) = \Large \frac{n^{1.000001}}{logn}$