search
Log In
0 votes
229 views

Find the complexity of the following code fragment:


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

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

}
 

in Algorithms 229 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.

1 Answer

4 votes
 
Best answer
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
2 answers
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; } }
asked Sep 28, 2018 in Algorithms sushmita 236 views
0 votes
2 answers
2
251 views
FIND THE TIME COMPLEXITY int i=1,j; for(;i <= n;i + +) { for(j = i; j <= nlogn; j∗ = 2) { sum + +; } }
asked Sep 28, 2018 in Algorithms sushmita 251 views
0 votes
0 answers
3
110 views
State true/false f(n) != O(g(n)) and g(n) != O(f(n))
asked Sep 28, 2018 in Algorithms sushmita 110 views
0 votes
1 answer
4
377 views
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}$
asked Sep 28, 2018 in Algorithms sushmita 377 views
...