skpro19's blog

O(n^2) solution is getting accepted but O(n * (n — 1)) solution is getting TLE
By skpro19, history, 9 years ago, In English

The problem is Almost Arithmetic Sequences.

Accepted Solution

Time limit exceeded

Can someone please figure out why is this happening?

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

»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

O(n2) and O(n(n - 1)) is the same in terms of big O notation. Are you sure you need set in your programs? Your slower program is because you add O(n2) elements to set. Maybe list or vector will be enough? Or iterating over elements instead of a new structure?

→ Reply