Блог пользователя jha_gaurav98

Problem in determining time complexity
Автор jha_gaurav98, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
»
6 лет назад, # |
← Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

The time complexity is O(NlogN).

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

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить