Focus_2000's blog

Time Complexity of '+' with strings Giving TLE??
By Focus_2000, history, 3 years ago, In English

Problem: A. Cut and Paste when i am using

s=s+t; [this is giving me TLE on 37 test ] [128332169](https://mirror.codeforces.com/contest/1280/submission/128332169)

and s+=t; is Accepted 128332405 20 ms

can anyone tell me why such happen.???

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

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

s = s + t; this line will create new string object with value s + t and assign it to s, complexity $$$O(|s| + |t|)$$$

s += t; this line just simply append t to s, complexity $$$O(|t|)$$$

#include <bits/stdc++.h>
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    string s = "";

    time_t start = clock();
    for(int i = 0; i < 1000; i++) s = s + "a";
    cout << clock() - start << '\n';

    start = clock();
    for(int i = 0; i < 1000; i++) s += "a";
    cout << clock() - start;
}

This code produced the following output on my system

100
4

So avoid using assignment operator!

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks. Found where i am wrong.

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

    When I'm running your code on Dev C++ it is printing 0 0, but in the online C++ compiler, it is giving the right answer. Can you please tell me what is wrong with the Dev C++ compiler? Thank You:)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I guess CLOCKS_PER_SEC on your system has the value 1000. So just add consuming stuff between 2 clock() call, you'll see the difference:

      time_t start = clock();
BogoSort();
cout << clock() - start;

      For better precision, I suggest using chrono. IMO using clock() is better as it's really easy to remember the syntax.

      → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

I think the '+' operator's complexity is O(2*(n1 + n2)), where n1 and n2 are the lengths of the strings s and t.
The complexity of the operator '+=' might only be O(2*n2) in some implementations on the other hand as only the append() operation is to be performed.
A Stack Overflow Thread
If there is a huge difference between the lengths of s and t, this could effectively work out as the difference between an O(N) algorithm and an O(1) algorithm, and could possibly lead to TLE.

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

Click

→ Reply