wiaderko69's blog

By wiaderko69, history, 15 months ago, In English

Can someone tell me what's the time complexity of this code? I thought it's O(N^2) because of vector erase but it gets AC 332397335.

Code
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by wiaderko69 (previous revision, new revision, compare).

»
15 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

It's O(N)

»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Your code is indeed $$$\mathcal{O}(n^2)$$$ consider a case where $$$c = 2$$$ and $$$a$$$ consists of $$$x$$$ ones, next $$$x+1$$$ twos and finally $$$1$$$ one; $$$n$$$ would be equal to $$$2x+2$$$.