Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

At least GCC was (and by now Clang and probably others are) known for occasionally optimizing out certain uses of functions like strlen(), which can change the time complexity in some trivial cases.

For instance, if you consider strcmp(x, y, strlen(y)) where x is of fixed length, then the whole function would be constant-time if strlen(y) is optimized out, whereas it would take linear time (linear in strlen(y)) otherwise. GCC et al. can optimize out strlen() in some such cases.

In practice you wouldn't want to rely on this, both because compilers aren't anywhere near smart enough to figure out complicated cases and also because these wouldn't happen in debug mode either, but it's not impossible for time complexity to change through optimization.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: