TLE issue - is .index() method slow in Python?

Question

Forgive me if I come off as a bit novice, I started teaching myself how to code just a few weeks ago.

I've been working through a problem set at cses.fi. I came across the "collecting numbers" problem which essentially asks us: given an array, such as [4, 2, 1, 5, 3], how many times would we have to "collect" the numbers such that the numbers are organized in increasing order from 1 to n.

In this particular case we would need 3 rounds, as we iterate once and collect "1", a second iteration gives us "2, 3", and finally a third will give us "4, 5".

I am programming in Python and came across the solution eventually, though I was getting a TLE error when submitting it. I made a number of tweaks and discovered that .method() was slowing my code considerably.

TLE code:

n = int(input())
arr = list(map(int, input().split()))
i_arr = [0] * (n + 1)
res = 1
 
for i in arr:
    i_arr[i] = arr.index(i)
for i in range(1, len(i_arr)):
    if i_arr[i] < i_arr[i - 1]:
        res += 1
 
print(res)

Accepted code with 0.09s run time:

n = int(input())
arr = list(map(int, input().split()))
i_arr = [0] * (n + 1)
for i in range(n):
    i_arr[arr[i]] = i
res = 1
for i in range(1, len(i_arr)):
    if i_arr[i] < i_arr[i - 1]:
        res += 1
 
print(res)

The only difference between these two blocks of code are in the way I index in my first for loops.

My question is: is the ,index method slow in python? and if yes, why exactly? Thanks for any help.

Answer 1

Yes it will be much slower, especially as the size of 'n' grows.

In the TLE Code, what you're saying is:

• find the index of 'i' by searching through the array for 'i'. Remember that the python program cannot assume that the list is ordered or anything, so it will have to do a manual search for the first occurrence of 'i'
• this is fine when 'n' is small, because for example during the first iteration, .index() will first look for i=0 and return quickly because the first number in the list happens to be 0.
• but think about as n grows, you're basically asking .index() to traverse the list +1 more spot each time
• this for-loop is what is known as an O(n^2) algorithm, because for each 'i' within 'n', the worst case is searching through n items to find the index to return. The worse case happens at the last iteration of the for-loop.

Your second implementation does not require traversing the list n-times like your first implementation does.

Of course, like I mentioned, the first implementation will not have to traverse the entire list every time, but it gets worse as the loop goes on and as 'i' grows.