Why is one code faster than other even when iterations are more?

Question

My code is short and has lesser number of iterations than the other but still it gets a time limit exceeded error while the other code is accepted on codechef.com. The codes are solution to the "Ambiguous permutation" problem on codechef.com Why is this code:

def inverse(data,x):

    temp=[]

    for i in range(x):
        temp.append(0)
    for i in range(x):
        temp[data[i]-1]=i+1
    return temp

def main():

    while 1:
        x=input()
        if not x:
            return
        data=raw_input().split(' ')
        for i in range(len(data)):
            data[i]=int(data[i])
        temp = inverse(data,x)
        if temp==data:
            print 'ambiguous'
        else:
            print 'not ambiguous'

if __name__ == "__main__":
    main()

faster than this code:

while True:

    output=[]
    n= input()
    if n==0: break
    caseList= raw_input().split()
    amb=1
    for i in range(1, n+1):
        output.append(str(caseList.index(str(i))+1))

    if output==caseList:
        print ("ambiguous")
    else:
        print ("not ambiguous")    

Please help me out...

Answer 1

When such a consistent time difference shows up, we are not talking about something that is 2, or 3 times slower - if one method passes, and the other always times out, it is a huge time difference- normally tied to algorithm complexity.

Although the first code has plenty of room to get better (usage of xrange instead of range, for example), in the final array, the result is update by random access, straight by the index caculated by data[i] - 1- while in the second snippet, you use caseList.index(str(i)) to retrieve each index. The "index" lisr method performs a linear search on the list, starting at the beginning. It may seem little, but when it is doen for each element in the list, your algorithm which was O(N) becomes O(N²) - which expains the dramatic speed down in this second form.