Saksham_Sahgal's blog

Two submissions with same Complexity , one gets TLE and other AC
By Saksham_Sahgal, history, 3 years ago, In English

i recently encountered a problem — 1208B - Уникальность

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?

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

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply