CODEWITHSUNDEEP
pythonfunctiontime-complexitybuilt-inspace-complexity
noobprogrammer
noobprogrammer

Reputation: 109

Time/space complexity of in-built python functions

What is the time/space complexity of split/strip/open (in-built python functions)?

Does anyone know where i can look up on the time/space complexity of these functions?

Upvotes: 3

Views: 15664

Answers (1)

Adam
Adam

Reputation: 424

The exact answer will depend on what properties are fed into the function. The easiest way to find out would probably be to examine the source code for those functions. The python source code can be found here.

Lets take a look at the source for split. The code runs different loops depending on the properties. This is the loop for splitting by whitespace.

    while (maxcount-- > 0) {
    while (i < str_len && STRINGLIB_ISSPACE(str[i]))
        i++;
    if (i == str_len) break;
    j = i; i++;
    while (i < str_len && !STRINGLIB_ISSPACE(str[i]))
        i++;

In this code, the function will look at each character in the string (unless the maxcount is reached). The inner most loops will run n times for a string of size n. Time complexity is O(n)

The source for strip steps through each character in the string.

    i = 0;
if (striptype != RIGHTSTRIP) {
    while (i < len) {
        Py_UCS4 ch = PyUnicode_READ(kind, data, i);
        if (!BLOOM(sepmask, ch))
            break;
        if (PyUnicode_FindChar(sepobj, ch, 0, seplen, 1) < 0)
            break;
        i++;
    }
}

j = len;
if (striptype != LEFTSTRIP) {
    j--;
    while (j >= i) {
        Py_UCS4 ch = PyUnicode_READ(kind, data, j);
        if (!BLOOM(sepmask, ch))
            break;
        if (PyUnicode_FindChar(sepobj, ch, 0, seplen, 1) < 0)
            break;
        j--;
    }

    j++;
}

This gives strip a time complexity of O(n).

The Source for open() shows no loops. This is what we would expect. There is nothing to loop through.

Upvotes: 9

Related Questions