Search code examples
cstringtime-complexitystrncmp

Complexity of strncmp in string.h

I would like to know the time complexity of int strncmp(const char *__s1, const char *__s2, size_t __n) which is in the C library(string.h).

I have to study the complexity of my whole program which is calling strncmp thousands of time, I can't ignore this complexity.
Where can I find documentation about the complexity of c library function ?

Solution

  • The standard imposes no requirements on the complexity. That is entirely up to the implementation. But there's absolutely no reason to expect it to be anything else than O(__n)

    • It's trivial to write an implementation that satisfies O(__n), so there's no reason to suspect that a real implementation made by professionals is worse.

    • It's impossible to write an implementation that is better than O(__n), so that will not happen.

    But if you want to be sure, you have to study the particular implementation you're using.