rookiegang's blog

String complexity
By rookiegang, history, 6 years ago, In English

What is complexity of adding char in front of the string like s = c + s?

Because when I tested on c++ with code, its like O(1), but i think (but not sure then i ask here) i ever submitted at codeforces with this method, in O(n) loop then its get TLE (so the complexity O(n^2)), then i changed that part with other O(1) part then got AC.

What is complexity of adding on string like s = s2 + s1 with s1 is small string with length < 10 and s2 is n-long string?
What is complexity of adding on string like s = s1 + s2 with s1 is small string with length < 10 and s2 is n-long string?

Thank you codeforces community

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

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

Adding a char in front of a string is always linear in length of the string.

In general, concatenating two strings will be linear in lengths of both strings.

However, if the first string is an rvalue, then the second one will be just appended to it. If appending doesn't cause the first string to reach its capacity, you can expect it to take time proportional to the length of the second string.

For example, the following code will take O(N^2) time:

    std::string a;
    for (int i = 0; i < N; ++i) {
      a = a + "xy";
    }

And the following code will take O(N) time:

    std::string a;
    for (int i = 0; i < N; ++i) {
      a = std::move(a) + "xy";
    }
→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    wait , so for O(1) operation , I can add character in front of the string through second way( using move method ).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Unfortunately not. You can think of the second example as reusing memory of a and appending "xy" to it.

      You can think of adding a character in the front as s.insert(s.begin(), c), which is linear. Whether we reuse memory of a to create s or we make a copy won't change the complexity.

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

    Also worth noting: a = a + "xy" is O(N) while a += "xy" is O(1) (amortized).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain further why is it so?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        a = a + "xy" creates a copy of a, appends "xy" and then assigns it back to a.

        a += "xy" just appends "xy" to a.

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

      how is it possible? from where you know all these things?

      → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      blowed my mind , Thanks

      → Reply