CODEWITHSUNDEEP
pythonlisttime-complexity
Fairly Nerdy
Fairly Nerdy

Reputation: 903

What is the time complexity of Python List Reverse?

I have seen this page https://wiki.python.org/moin/TimeComplexity but I don't see the reverse() function in there for lists. What is the time time complexity of list's reverse()?

My experiments with time indicate that it is O(n) for larger sizes. Can anyone confirm it ?

timeit Time to reverse a list of size

   10    .1027
  100    .2347
 1000    .6704
10000   6.204
20000  12.9

Upvotes: 34

Views: 51513

Answers (4)

CreatorGhost
CreatorGhost

Reputation: 387

Reversing a list either through an in-built library like reverse() or by using slicing a=a[::--] both are going to take the same amount of time i.e O(n)

Upvotes: 4

Anatolii
Anatolii

Reputation: 14660

If you look into the implementation of the reverse method here, then it looks as follows:

static PyObject *
listreverse(PyListObject *self)
{
    if (Py_SIZE(self) > 1)
        reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
    Py_RETURN_NONE;
}

So, the operation is actually delegated to reverse_slice. Then, let's look into it:

static void
reverse_slice(PyObject **lo, PyObject **hi)
{
    assert(lo && hi);

    --hi;
    while (lo < hi) {
        PyObject *t = *lo;
        *lo = *hi;
        *hi = t;
        ++lo;
        --hi;
    }
}

So, here are 2 indices initially set at the start and end of the list. Then, at each iteration of while loop, elements at respective indices are swapped:

PyObject *t = *lo;
*lo = *hi;
*hi = t;

And then the left index gets incremented and the right one decremented:

++lo;
--hi;

The loop goes on as long as the right index exceeds the left one. So, if there're n elements in the list, then there will be performed n/2 iterations and hence the time complexity is O(n)

Upvotes: 37

Zig Razor
Zig Razor

Reputation: 3495

If you see the algorithm is easy to view that the time complexity of reverse is O(n) (linear time complexity) where n is the number of the element in the list.

Upvotes: 3

Serenity
Serenity

Reputation: 36635

Yes, you are right, it is O(n) where n - length of list. Look here for more information: https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

Upvotes: 39

Related Questions