What's The Runtime Of Python's Strip()?

What's the runtime of Python's strip()? Since remove is O(n) for a single char, is strip O(n^2) for a string?

Solution 1:

It is also O(N) only. Quoting the code corresponding to the plain strip which strips the spaces, from the version 2.7.9

Py_LOCAL_INLINE(PyObject *)
do_strip(PyStringObject *self, int striptype)
{
    char *s = PyString_AS_STRING(self);
    Py_ssize_t len = PyString_GET_SIZE(self), i, j;

    i = 0;
    if (striptype != RIGHTSTRIP) {
        while (i < len && isspace(Py_CHARMASK(s[i]))) {
            i++;
        }
    }

    j = len;
    if (striptype != LEFTSTRIP) {
        do {
            j--;
        } while (j >= i && isspace(Py_CHARMASK(s[j])));
        j++;
    }

    if (i == 0 && j == len && PyString_CheckExact(self)) {
        Py_INCREF(self);
        return (PyObject*)self;
    }
    elsereturn PyString_FromStringAndSize(s+i, j-i);
}

It first starts from the left and increments the variable i, till it finds a non-space character and then it starts from the right and decrements j till it finds a non-space character. And finally the string between i and j is returned with this

PyString_FromStringAndSize(s+i, j-i)

But on the other hand, the strip which removes the set of characters, is slightly complicated but fairly similar.

Py_LOCAL_INLINE(PyObject *)
do_xstrip(PyStringObject *self, int striptype, PyObject *sepobj)
{
    char *s = PyString_AS_STRING(self);
    Py_ssize_t len = PyString_GET_SIZE(self);
    char *sep = PyString_AS_STRING(sepobj);
    Py_ssize_t seplen = PyString_GET_SIZE(sepobj);
    Py_ssize_t i, j;

    i = 0;
    if (striptype != RIGHTSTRIP) {
        while (i < len && memchr(sep, Py_CHARMASK(s[i]), seplen)) {
            i++;
        }
    }

    j = len;
    if (striptype != LEFTSTRIP) {
        do {
            j--;
        } while (j >= i && memchr(sep, Py_CHARMASK(s[j]), seplen));
        j++;
    }

    if (i == 0 && j == len && PyString_CheckExact(self)) {
        Py_INCREF(self);
        return (PyObject*)self;
    }
    elsereturn PyString_FromStringAndSize(s+i, j-i);
}

It is the same as the previous one, but it has the extra memchr(sep, Py_CHARMASK(s[j]), seplen) check every time. So, the time complexity of this becomes O(N * M), where M is the length of the actual string of characters to be stripped.