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

Two submissions with same Complexity , one gets TLE and other AC
Автор Saksham_Sahgal, история, 2 года назад, По-английски

i recently encountered a problem — 1208B - Uniqueness

I have use a simple Binary search approach for that problem

I have 2 submissions , both are using Binary search and both have same worst case time complexity of O(N^2 log^2(N)) but one gives TLE and the other gets AC

AC submission — 146479295

TLE Submission — 146333083

can anyone tell me why this is happening?

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

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

I mean, the AC code is already close to the time limit, and using sets has bigger constant factor than just sorting, it's pretty reasonable for the second code to TLE

Time complexity is more of an estimation than a guarantee that your algorithm will be fast

→ Ответить