I have to find the time complexity of the below code. But got confused as the j is increasing acccording to the value of i.
Else I thought it would be $O(n^2)$.
#include <iostream>
using namespace std;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j+=i)
{
//Some O(1) Code
}
}
As others have stated, assuming $n > 0$ then on the first iteration of the outer loop the inner loop will have increment 0 and never terminate.
If instead you meant for the inner loop to increment by i+1, then the total number of iterations is given as:
Link to latex: I don't have enough reputation to embed images.
Where H_n is the n-th harmonic number.
So complexity is O(n log n).
The time complexity is not defined for this function since it doesn't terminate on all inputs. In fact, it only terminates for n <= 0.
nis anything above 0, you would have a non-terminating program.nis just a variable which a user can give any valuen>0the execution time will be infinite, as in the very first iteration of the outer loopi=0, so the increment of the inner loop will bej=j+0, causingjro remain 0 forever.n <0, instead, the outer loop condition will be false since the very first iteration, so//Some O(1) Codewill never be executed.