jha_gaurav98's blog

Problem in determining time complexity
By jha_gaurav98, history, 6 years ago, In English

What will be the time complexity of the following nested loop:

for(int i=2;i<n;++i){
    for(int j=i;j<n;j+=i){
        //some code here
    }
}

Actually I was participating in a competition on Codechef last night. And there was a question for which I thought of a solution like this. But the range of n was [2, 106] and time limit was 1.5s. So I thought that my solution will exceed the time limit and hence I didn't submit it. But after the contest I saw another guy submitting the same solution and getting his solution accepted. So, can someone tell what is the exact time complexity of this code snippet?

Link for question

Thanks in advance

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The runtime is not O(N^2) because it is j+=i, not j++. It is (N + N/2 + N/3 +...+ N/N). On way to see if the code will run in time is to run the loops locally.

Here is what I ran:

int n = 1000000;
int out = 0;
for(int i=2;i<n;++i){
    for(int j=i;j<n;j+=i){
        out++;
    }
}
cout << out<<endl;

The loop ran 12,969,986 times (that is what the code printed) which isn't that many operations. 500,000,000 or higher is when there is a risk for TLE.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's a great way to check the upper bound on number of times the loop will run. I will try this from next time.But can you comment a bit about the complexity? Is it like linear. Thanks

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does this graph look familiar to you? http://www.wolframalpha.com/input/?i=N+%2B+N%2F2+%2B+N%2F3+%2B...%2B+N%2FN

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you wanna conclude that the complexity is almost linear?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      It's close enough to linear that you can ignore the harmonic series coefficient

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for telling that. I will remember this thing in future

        → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Here you are basically doing N in the first iteration. In the second iteration, the ur skipping 1 element in each updation so its N/2 operations. in the third operation ur skipping 2 element in each updation so it is running n/3 times and so on. So total number of operations is n + n/2 + n/3 + n/4 ... which is N(1 + 1/2 + 1/3 + 1/4 .. 1/n) This is a very well known fact that 1 + 1/2 + 1/3 + 1/4 ... is bounded by logn. So overall complexity is NlogN.

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

The time complexity is O(NlogN).

By evaluating with the integral of ,The following inequality can be shown.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

it's nearly O(N*Log(N))

→ Reply