CODEWITHSUNDEEP
c++complexity-theory
Bagpuss
Bagpuss

Reputation: 43

Order of Complexity of standard lib functions

Sorry if this is a stupid question, but...

The order of Complexity of this code is O(n):

char buf[] = "hello world";
size_t length = strlen(buf);

for(size_t i = 0; i < length; i++)
{
    //do stuff
}

and this code is O(n^2):

char buf[] = "hello world";
for(size_t i = 0; i < strlen(buf); i++)
{
    //do stuff
}

because strlen is O(n).

But who says that strlen is O(n), is it defined in the standard, does it have to be O(n)?

How can I know for sure what the Order of Complexity of any standard function is going to be?

Upvotes: 2

Views: 2167

Answers (3)

Bo Persson
Bo Persson

Reputation: 92331

Yes, strlen is O(n), but in this particular example (with a string literal) a good optimizer can replace strlen(buf) with sizeof(buf). Some compilers do.

Upvotes: 1

AProgrammer
AProgrammer

Reputation: 52314

Some functions have their complexity defined in the standard. Others, included those inherited from C, don't. For those, you can't rely on anything else than quality of implementation to keep it at the minimum.

Upvotes: 1

sharptooth
sharptooth

Reputation: 170509

Yes, it has to be at least O(n) by design - it receives the address of the first character and has to find the null character by scanning along the string and it can only do so by advancing and checking each character.

Upvotes: 6

Related Questions