CODEWITHSUNDEEP
c++algorithmstl
AarCee
AarCee

Reputation: 863

Considering complexity of STL container operations

Do we factor-in the time/space complexities of STL container operations when calculating the complexity of an algorithm? For example, given the following code snippet:

// str is an std::string, and size = str.size()
std::string res;
for (int i = 0; i < size; i++)  // size is some integer
    res += str[i];

Is the time complexity of the above code snippet: O(size) because of the loop?

OR

O(size^2): because in each loop iteration we're appending to an std::string and that is a linear time complexity operation?

If there is no generic answer, I'm asking what do we need to consider when in an interview. Is there a kind of a de-facto convention to consider/ignore STL containers operations' time/space complexities?

Thanks.

EDIT:

Even if the example code doesn't show the complete picture, my question is whether the complexities of STL container operations need to be taken into account in calculating the complexity of an algorithm.

Upvotes: 1

Views: 876

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726599

Of course you need to consider the complexity of the individual operations, regardless of whether it happens in your code or inside a library function. In fact, Standard C++ Library specifies the time complexity of operations on its containers, and also the time complexity of its algorithms, in order to make your computations possible.

In your specific example the answer depends on the sizes of individual str elements in the array of strings str[]. If the length of each element string is roughly size, then the answer is O(size2). If each element has a fixed size, then the answer is O(size), because the constant length can be factored out of the expression.

Upvotes: 1

Related Questions