Nguyen_Khac_Trung's blog

By Nguyen_Khac_Trung, history, 3 months ago, In English

What is the complexity of st.erase(st.begin())?

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

»
3 months ago, # |
  Vote: I like it +14 Vote: I do not like it

It should be O(logn)

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    for(r=0;r<b.size();r++) tmp+=a[r];
    if (tmp==b) res.pb(1);
    while (r<a.size())
        {
            tmp.erase(tmp.begin());
            tmp+=a[r++];l++;
            if (tmp==b) res.pb(l+1);
        }

    so this code will has O(NlogN), right? :>

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If I understand correctly, inside the while cycle you are comparing a set to another set, which has roughly O(n^2) complexity

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

What st is? What cppreference tell about it?

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

For a set, the complexity would be O(logn)

»
3 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Is st a set? If so, then it's O(log n), but it seems like your st is a string, in which case it's O(n).