CODEWITHSUNDEEP
pythontime-complexity
Robin Andrews
Robin Andrews

Reputation: 3794

Time complexity of Python Function Involving List Operations

When I plot the time taken for the following algorithm for different size input, the time complexity appears to be polynomial. I'm not sure which operations account for this.

I'm assuming it's to do with list(s), del l[i] and l[::-1], but I'm not clear what the complexity of these is individually. Can anyone please explain?

Also, is there a way to optimize the algorithm without completely changing the approach? (I know there is a way to bring it down to linear time complexity by using "double-ended pincer-movement".)

def palindrome_index(s):
    for i, c in enumerate(s):
        l = list(s)
        del l[i]
        if l[::-1] == l:
            return i
    return -1

Upvotes: 0

Views: 195

Answers (2)

zvone
zvone

Reputation: 19332

All of these are linear "O(n)":

list(s)

list(s) creates a new list from s. To do that, it has to go through all elements in s, so its time is proportional to the length of s.

l[::-1]

Just like list(s), l[::-1] creates a new list with the same elements as l, but in different order. It has to touch each element once, so its time is proportional to the length of l.

del l[i]

In order to delete an element at position i, the element which was at position i+1 has to be moved to position i, then element which was at i+2 has to be moved to position i+1 etc. So, if you are deleting the first element (del l[0]), it has to touch move elements of the list and if you are deleting the last (del l[-1]), it just has to remove the last. On average, it will move n/2 elements, so it is also linear.

Upvotes: 1

Ami Tavory
Ami Tavory

Reputation: 76297

Your algorithm indeed is quadratic in len(s):

In iteration i, you perform linear time operations in the length: creating the list, reversing it, and (on linear on average) erasing element i. Since you perform this len(s) times, it is quadratic in len(s).

I'm assuming it's to do with list(s), del l[i] and l[::-1], but I'm not clear what the complexity of these is individually. Can anyone please explain?

Each of these operations is linear time (at least on average, which is enough to analyze your algorithm). Constructing a list, either from an iterable, or by reversing an existing list, is linear in the length of the list. Deleting element i, at the very least, requires about n - i + 1 shifts of the elements, as each one is moved back once.

Upvotes: 1

Related Questions