Search code examples
pythontime-complexityspace-complexity

What is the time complexity and space complexity of array[::-1]

When reverse a list in Python, I usually use the array[::-1] for reversing and I know that a more common way might swap from two sides of the list. But I'm not sure the difference between these two solutions such as time complexity and space complexity.

Code for this two methods below:

def reverse(array):
    array[:] = array[::-1]


def reverse(array):
    start, end = 0, len(array)-1
    while start < end:
        array[start], array[end] = array[end], array[start]
        start += 1
        end -= 1
Solution

  • In C python, assuming array is a list, the expression array[::-1] triggers the following algorithm found in function list_subscript() in the source file listobject.c

    result = PyList_New(slicelength);
if (!result) return NULL;

src = self->ob_item;
dest = ((PyListObject *)result)->ob_item;
for (cur = start, i = 0; i < slicelength;
     cur += (size_t)step, i++) {
    it = src[cur];
    Py_INCREF(it);
    dest[i] = it;
}

    Both time and space complexity of this piece of code are O(n) where n is the length of the list. Of course there is no suprise here.

    Your function reverse() has also O(n) time complexity, the difference is that it does not use a temporary list.

    The built-in C function is much faster than the pure python loop (about 10 times on my computer for a 100 elements list).