CODEWITHSUNDEEP
c
allstar
allstar

Reputation: 1205

complexity of array vs string length

I believe that sizeof an array is of O(1) complexity.

A string is a character array, but I heard that strlen is of O(n) complexity, scanning the string until the terminating null. Why isn't it also O(1)?

Upvotes: 0

Views: 590

Answers (2)

Barmar
Barmar

Reputation: 782148

sizeof just gets the size based on the type declaration. It doesn't care about the contents, and it's calculated at compile time.

strlen() has to scan the array looking for the null byte, as you said. This is O(n).

They give different answers.

char s[1000] = "abc";
printf("sizeof = %d strlen = %d\n", sizeof s, strlen(s)); // prints 1000 and 3
strcpy(s, "1234567890123456789012345678901234567890");
printf("sizeof = %d strlen = %d\n", sizeof s, strlen(s)); // prints 1000 and 40

If you call strlen() on a string literal, the compiler can optimize it and calculate the size at compile time. So strlen("foo") will likely be O(1).

Upvotes: 2

Daniele Cappuccio
Daniele Cappuccio

Reputation: 2202

sizeof() operator is completely managed by the C compiler. Once your program has been compiled, take a look to your object file to see that all sizeof() have been converted to constants.

strlen(), on the other hand, steps into the memory starting from the pointer specified as an argument until it finds a 0x00 value (NULL)

Upvotes: 0

Related Questions