wiaderko69's blog

By wiaderko69, history, 13 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

»
13 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).

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

It's O(N)

»
13 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

Unable to parse markup [type=CF_MATHJAX]

and

Unable to parse markup [type=CF_MATHJAX]

consists of

Unable to parse markup [type=CF_MATHJAX]

ones, next

Unable to parse markup [type=CF_MATHJAX]

twos and finally

Unable to parse markup [type=CF_MATHJAX]

one;

Unable to parse markup [type=CF_MATHJAX]

would be equal to

Unable to parse markup [type=CF_MATHJAX]

.