What is the time complexity of Python List Reverse?
Solution 1
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
Solution 2
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)
Solution 3
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)
Solution 4
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.
Fairly Nerdy
Updated on June 26, 2020Comments
-
Fairly Nerdy almost 4 years
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 oflist
'sreverse()
?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