Complexity for two approaches of finding next biggest palindrome of a number I have come up with a problem online about the next biggest palindrome of a number and i have solved the problem by two different approaches in python. The first one is,

t = long(raw_input())

for i in range(t):
    a = (raw_input())
    a = str(int(a) + 1)
    palin = ""
    oddOrEven = len(a) % 2

    if oddOrEven:
        size = len(a) / 2
        center = a[size]
    else:
        size = 0
        center = ''

    firsthalf = a[0 : len(a)/2]
    secondhalf = firsthalf[::-1]
    palin = firsthalf + center + secondhalf

    if (int(palin) &lt; int(a)):
        if(size == 0):
            firsthalf = str(int(firsthalf) + 1)
            secondhalf = firsthalf[::-1]
            palin = firsthalf + secondhalf

        elif(size &gt; 0):
            lastvalue = int(center) + 1

            if (lastvalue == 10):
                firsthalf = str(int(firsthalf) + 1)
                secondhalf = firsthalf[::-1]
                palin = firsthalf + "0" + secondhalf

            else:
                palin = firsthalf + str(lastvalue) + secondhalf
    print palin


and the another one is,

def inc(left):
    leftlist=list(left)
    last = len(left)-1
    while leftlist[last]=='9':
        leftlist[last]='0'
        last-=1

    leftlist[last] = str(int(leftlist[last])+1)
    return "".join(leftlist)


def palin(number):
    size=len(number)
    odd=size%2
    if odd:
        center=number[size/2]
    else:
        center=''
    print center
    left=number[:size/2]
    right = left[::-1]
    pdrome = left + center + right
    if pdrome &gt; number:
        print pdrome
    else:
        if center:
            if center&lt;'9':
                center = str(int(center)+1)
                print left + center + right
                return
            else:
                center = '0'
        if left == len(left)*'9':
            print '1' + (len(number)-1)*'0' + '1'
        else:
            left = inc(left)
            print left + center + left[::-1]

if __name__=='__main__':
    t = long (raw_input())
    while t:
        palin(raw_input())
        t-=1


As a computer science perspective, what is the complexity of both of this algorithms? which one is more efficient to use?
I did some digging on this and i think the 2nd one is more efficient. I can not determine the complexity though but i know why the first one will take more time than the 2nd one.

In the first i approach, i did some arithmatic addition on the given input directly like here a = str(int(a) + 1) or here firsthalf = str(int(firsthalf) + 1) rather than just doing arithmatic on a single number like in the 2nd approach center = str(int(center)+1). So apparently a being a huge number and doing arithmatic on it will take a considerable amount of time.

This is the easiest explanation i can come up with. If anyone can do a more elaborate explanation with the given complexity for both the algorithms please feel free to do so.