xINFERNOx's blog

Time Complexity Variation
By xINFERNOx, history, 5 years ago, In English

Why the second code executes within 500ms whereas the first one gives TLE(2000ms) ?

1497E1 - Square-Free Division (easy version)

const int N = 1e7 + 5;
vector<int> maping(N);
int i,j;
Code 1
Code 2
  • Vote: I like it
  • -7
  • Vote: I do not like it

»
5 years ago, hide # |
← Rev. 2  
Vote: I like it +10 Vote: I do not like it

Overflow? int i, j; when i is around N, j is around N*N in the second implementation. So sometimes it gets negative and you do many iterations.

You avoid overflow in the first implementation because j*j increases by 2*j+1 each iteration so j*j doesn't go over N + O(sqrt(N))

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it -10 Vote: I do not like it

    I am using macro #define int long long so overflow should not be there

    → Reply
    • »
      »
      »
      5 years ago, hide # ^ |
       
      Vote: I like it +13 Vote: I do not like it

      Please format your blogs properly & don't forget to mention such important details next time. You should put some effort into describing your problem if you want to get help.

      Well, the first code is O(N*sqrt(N)) because j goes from 1 to sqrt(i).

      Second code is O(sum n/i^2) we know that O(sum n/i) = O(nlog(n)) therefore your second code is way faster asymptotically.

      → Reply