The Gateway to Computer Science Excellence
0 votes

Find the complexity of the following code fragment:

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

 for(i + +; i <= n; i + +)


in Algorithms by Boss (17.6k points) | 139 views
It should be O(nlogn).
its coming O(nlogn) for me.
Yes, Exactly.
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.

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.
by Active (1.2k points)
selected by
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 


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,306 answers
105,012 users