libc `strlen()` is O(n), but PHP strings are binary safe (i.e. http://3v4l.org/47iaP ) so it must be storing a length as part of the string zval. So PHP strlen should be constant time.

+1 for recommending checking the PHP source code to be sure, though