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

Time Complexity Variation
Автор xINFERNOx, история, 3 года назад, По-английски

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
  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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))

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

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

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

      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.

      → Ответить