C137's blog

String length complexity...
By C137, history, 9 years ago, In English

String str;

cin>>str;

for(int i=0;i<str.length();i++){

....

}

if str.length()=n, then the total complexity of the algorithm is n*n?? or just n?

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

Comments Comments (11)
| Write comment?
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Both string::size and string::length are synonyms and return the exact same value. Complexity : O(1).

→ Reply
»
9 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Here is the C program to find length of string.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it

Most modern compilers do an optimization with the function call being repeated without any changes, so instead it memorizes the value returned by that function, but still can not rely on compiler to do that and it's better to do it manually as the following:

for(int i=0, length=str.length(); i<length; ++i){

// your code

}

the code above runs in O(n) complexity instead of O(n^2), and it would be remarkable that the code runs faster for large strings lengths.

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

    This is true for strlen() but not for string::length(), because the former is O(n) and the latter is O(1).

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

    well i always store the length in a separate variable before the loop, but a friend told me that the complexity of length() is O(n) so i wanted to make sure about the information, thanks for the help :)

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

      The complexity for string::size()/length() is constant but of course it would be faster to store size in a variable (e.g. sz) because of:

      -Accessing (sz) is faster than accessing (string::size()/length())

      -Comparing int(i) to int(sz) is faster than comparing int(i) to unsigned int(string::size()/length())

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

read here http://www.cplusplus.com/reference/string/string/size/

→ Reply
»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

.

→ Reply