EternalFire's blog

Time complexity
By EternalFire, history, 6 years ago, In English

Hi,

so far I have known that the time complexity for concatenating two strings is O(n). So

while (a.length() < b.length()) a = "0" + a;

is O(n^2). But it still passed the TL: http://mirror.codeforces.com/contest/1066/submission/44198754

I am wondering why it passed. Could anyone help me?

  • Vote: I like it
  • +30
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It could be because of optimization. But I am not sure. See here

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Because it's stored in cache, the compiler sees that its doing same operation every time, it just predicts it will do it again in the next iteration so it adds it to cache.

→ Reply