retagged by
848 views
0 votes
0 votes

Find the complexity of the following code fragment:

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

1 Answer

Best answer
4 votes
4 votes
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

Related questions

1 votes
1 votes
2 answers
1
sushmita asked Sep 28, 2018
710 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 ...
0 votes
0 votes
2 answers
2
sushmita asked Sep 28, 2018
797 views
FIND THE TIME COMPLEXITYint i=1,j; for(;i <= n;i + +) { for(j = i; j <= nlogn; j∗= 2) { sum++; } }
1 votes
1 votes
1 answer
3
Shubhanshu asked May 9, 2017
629 views
How the worst case of merge sort is O(n^2) according to the given MIT assignment pdf:-explain ?
2 votes
2 votes
3 answers
4
sushmita asked Mar 21, 2017
7,031 views
For each group of functions, sort the functions in increasing order of asymptotic (big-O) complexity:$\begin{align*} &(a) \;\;f1(n) = n^{0.999999} * \log n \\ &(b) \;\;f2...