1,805 views
3 votes
3 votes
int loop(int n)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<n;j+=i)
            {
                -------------O(1)-------------
            }
        }
    }

What is the time complexity of above code segment?

3 Answers

Best answer
6 votes
6 votes

see for every value of i j iterates for n/i 
how bcoz of j+=i ,j+ki=n so k=(n-j)/i or n/i
so for i=1 cost=n/i=n
for i=2 cost=n/i=n/2
for i=3 cost=n/i=n/3
.
.
.
for i=n cost=n/i=1
so total cost=
n+n/2+n/3+.....+n/n
=n(1+1/2+1/3+......+1/n)
=nlogn

selected by
0 votes
0 votes
Approach bottom up for such questions. See how j loop runs.

 

first iteration it runs n times ( for i=1)

second iteration it runs n/2 times(for i=2)

third iteration it runs n/3 times(for i=3) so on last iteration it runs 1 time.

 

Now the sum of iterations is= n+n/2+n/3+.........+1( n times)

                                       =n(1+1/2+1/3+......+1/n)

                                      1+1/2+1/3+.....+1/n is nth Harmonic series and its complexity is theta(log n)

 

so, overall complexity is O(nlog n)
0 votes
0 votes
To  find number of terms in A.P

$\frac{last term- first term}{common difference} +1$

The time complexity will depend on both the for loop ,since the second for loop is dependent on the first for loop.So,the for loop will run as below:

                                                          Number of terms(approx.)

When  i=1    j=1,2,3.......n-1                     n/1

            i=2    j=1,3,5,7,...n-2                     n/2

            i=k    j=1,1+k,1+2k,1+3k...n-k              n/k

             :

             i=n                                                 n/n

  So ,total  time  =n/1+n/2+n/3+.....+1

                            n(1/1+1/2+1/3+......+1/n)

1+1/2+1/3+....1/n <-----logarithmic series =log n

Hence,time complexity=O(nlogn)

Related questions

0 votes
0 votes
1 answer
2
iarnav asked Jun 12, 2018
839 views
Given an sorted array in descending order, what will be the time complexity to delete the minimum element from this array?
1 votes
1 votes
2 answers
3
vishal chugh asked Jan 24, 2018
1,731 views
What is the worst case time complexity to find kth smallest element into an array of ‘n’ element?