Respuesta rápida: Revisando el código fuente. :)
Respuesta larga:
Tal como ponía en los comentarios a tu pregunta, la complejidad de las funciones propias de PHP no es algo que se hayan parado a estudiar detenidamente, al menos es lo que deduzco de una búsqueda rápida en Google. Lo que si he encontrado son otras preguntas en Stack Overflow (en inglés) en las que se preguntan algo parecido, pero más orientado a los arrays: https://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions, https://stackoverflow.com/questions/4566314/php-what-is-the-complexity-i-e-o1-on-of-the-function-count y https://stackoverflow.com/questions/32100086/php-built-in-functions-complexity-isanagramofpalindrome-function. De estas tres preguntas, la primera es la más completa. Aparte de eso, la otra opción que nos queda es revisar el código fuente de PHP para estudiar la complejidad de las funciones que nos interesen.
En la respuesta de Kenny ya hay una explicación de la complejidad, y de porque nos hace falta conocerla, así que no me extenderé por ese lado.
Revisando el código fuente de PHP (que puedes encontrar en Github, o en Php.net) podemos ver el código de la función implode (en este caso es el código correspondiente al PHP 5.6.31), en el archivo string.c:
PHPAPI void php_implode(zval *delim, zval *arr, zval *return_value TSRMLS_DC)
{
zval **tmp;
HashPosition pos;
smart_str implstr = {0};
int numelems, i = 0;
zval tmp_val;
int str_len;
numelems = zend_hash_num_elements(Z_ARRVAL_P(arr));
if (numelems == 0) {
RETURN_EMPTY_STRING();
}
zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(arr), &pos);
while (zend_hash_get_current_data_ex(Z_ARRVAL_P(arr), (void **) &tmp, &pos) == SUCCESS) {
switch ((*tmp)->type) {
case IS_STRING:
smart_str_appendl(&implstr, Z_STRVAL_PP(tmp), Z_STRLEN_PP(tmp));
break;
case IS_LONG: {
char stmp[MAX_LENGTH_OF_LONG + 1];
str_len = slprintf(stmp, sizeof(stmp), "%ld", Z_LVAL_PP(tmp));
smart_str_appendl(&implstr, stmp, str_len);
}
break;
case IS_BOOL:
if (Z_LVAL_PP(tmp) == 1) {
smart_str_appendl(&implstr, "1", sizeof("1")-1);
}
break;
case IS_NULL:
break;
case IS_DOUBLE: {
char *stmp;
str_len = spprintf(&stmp, 0, "%.*G", (int) EG(precision), Z_DVAL_PP(tmp));
smart_str_appendl(&implstr, stmp, str_len);
efree(stmp);
}
break;
case IS_OBJECT: {
int copy;
zval expr;
zend_make_printable_zval(*tmp, &expr, ©);
smart_str_appendl(&implstr, Z_STRVAL(expr), Z_STRLEN(expr));
if (copy) {
zval_dtor(&expr);
}
}
break;
default:
tmp_val = **tmp;
zval_copy_ctor(&tmp_val);
convert_to_string(&tmp_val);
smart_str_appendl(&implstr, Z_STRVAL(tmp_val), Z_STRLEN(tmp_val));
zval_dtor(&tmp_val);
break;
}
if (++i != numelems) {
smart_str_appendl(&implstr, Z_STRVAL_P(delim), Z_STRLEN_P(delim));
}
zend_hash_move_forward_ex(Z_ARRVAL_P(arr), &pos);
}
smart_str_0(&implstr);
if (implstr.len) {
RETURN_STRINGL(implstr.c, implstr.len, 0);
} else {
smart_str_free(&implstr);
RETURN_EMPTY_STRING();
}
}
/* }}} */
Nota: hace mucho tiempo que no calculo la complejidad de una función, así que seguramente habré metido la pata en algún sitio. Se aceptan correcciones.
Sin entrar en muchos detalles, vemos que el código está en C (no en C++ como puse en los comentarios), y en el caso concreto (implode) hay una función C, llamada implode (no la he copiado), que realiza la función de extraer los parámetros de la llamada a implode desde el código PHP, verificar que estos sean correctos, realizar alguna conversión, y por último llamar a php_implode, que es la función que realiza el trabajo. Para este ejemplo voy a ignorar la complejidad de la función que realiza las comprobaciones, ya que dependerá de como trabaja internamente el intérprete de PHP (haciendo una apuesta, podría estar entre O(log n) y O(n)... quizás un poco más pero no creo que llegue a O(n*n)...).
Revisando ya la función php_implode (la que hace el trabajo de verdad), vemos que hay un par de llamadas a funciones internas, una que obtiene el total de elementos del array y otra que un puntero al primer elemento válido del array. La complejidad de la primera es O(1) y y la de la segunda es O(n) en el peor de los casos.
Después tenemos un bucle que recorre cada uno de los elementos del array -O(n)-, obteniendo cada uno de los valores almacenados en este -O(1)-. Dependiendo del tipo de dato guardado lo convierte a una cadena y lo concatena con el resultado actual. La complejidad de la concatenación es O(m) (depende de la longitud de la cadena a concatenar), pero en nuestro caso la podemos considerar un valor constante O(1). La conversión, aunque variará dependiendo del tipo de datos, vamos a considerarla O(2m), ya que en el peor de los casos tiene que copiar cadenas un par de veces.
Todo esto es mucho rollo buscando la complejidad de cada función que utiliza implode, pero al final nos quedará una fórmula como esta: O(1)+O(n)+O(n)*(O(1)+O(2m)+O(1))... Simplificando la fórmula nos quedaría
- O(n) en el mejor de los casos (todos los elementos del array son cadenas, y el array no tiene elementos borrados al principio),
- O(n)+O(2n*2m) en el peor (el array tiene un montón de elementos borrados al principio y los elementos son todos de tipos complejos que hay que convertir a cadena)
Trabajando en web, que es lo más habitual, la mayoría de las veces que utilicemos esta función seguramente solo contendrá cadenas, por lo que normalmente su complejidad será O(n).
Conclusión
Calcular la complejidad de una función interna de un proceso es una tarea simple pero tediosa, ya que exige tiempo (hacer este cálculo me ha llevado más de media hora, revisando ficheros de código que no había visto hasta el día de hoy para buscar las funciones e intentando comprender que hace cada una de ellas). A grandes rasgos podemos llegar a calcularla, aunque como dice
Kenny, normalmente los problemas de rendimiento que podemos encontrarnos no son por culpa del lenguaje de programación utilizado, sino porque no le estamos dando la mejor solución al problema que queremos resolver, o no estamos utilizando la herramienta adecuada dentro del lenguaje. Enlazo un artículo de 2005 de Joel Spolsky: De vuelta a las bases en el que el autor viene a decir que con los lenguajes actuales, muchas veces se desconoce como funcionan estos por debajo y se terminan desarrollando soluciones que son ineficaces.