Time and space complexity of base conversion code I have an algorithm that performs the base conversion. The input is a string and two ints b1 and b2. The string represents an int in base b1 and converts it into base in b2.

My code is:

def convert_base(num_as_string, b1, b2):
    if num_as_string == '0' or num_as_string == '-0':
        return num_as_string
    base10, degree = 0, 0
    is_neg = False
    if num_as_string[0] == '-':
        is_neg, num_as_string = True, num_as_string[1:]
    if b1 == 10:
        base10 = int(num_as_string)
    else:
        for digit in num_as_string[::-1]:
            base10 += string.hexdigits.index(digit.lower()) * (b1 ** degree)
            degree += 1
    if b2 == 10:
        return '-' + str(base10) if is_neg else str(base10)
    converted = []
    while base10 &gt; 0:
        digit = base10 % b2
        converted.append(digit)
        base10 //= b2
    res = ''
    for i in converted[::-1]:
        res += string.hexdigits[i].upper()
    return '-' + res if is_neg else res


Now I am trying to see if this can be improved in terms of time and space complexity. But I am not sure how to analyze the complexity of this code.

I know everything is constant before for digit in num_as_string[::-1]:. In this loop, it's just `O(n) where n is just number of digits of the input. 

Then in while base10 &gt; 0, it runs the look while base10 becomes 0. So, this would be something like O(number of digits in base10)

Finally, on for i in converted[::-1], this would also be O(number of digits in base10).

So, I am assuming the time complexity of this code is something like O(n) + 2 * O(number of digits in base10) which is linear.

For space, I am assuming it's O(number of digits in base10) because I store it in converted list. 

Are my observations correct? If not, what am I missing? Also, can this code be improved in terms of time and space complexity?

Thanks
Much of the following feedback is not really performance-related, but will make the code more easily legible and easily analyzed for the purposes of performance improvement.

Add type hints

b1 and b2 are presumably int, so add : int after their declaration. num_as_string and the function's return value are both str.

Multiple assignment

...has its limited applications, and in this case:

is_neg, num_as_string = True, num_as_string[1:]


there's not really an advantage to combining these two statements. Just do them separately, for legibility.

Exponentiation

You do this:

        base10 += string.hexdigits.index(digit.lower()) * (b1 ** degree)
        degree += 1


But rather than maintaining degree as a number that increases linearly, it's probably a better idea to maintain a number that increases by a multiplicative factor of b1 on every iteration.

Separation of concerns

Fundamentally, convert_base is doing two different things: parsing a string given a particular base into a number, and formatting a number given a particular base into a string. So just make two functions. It's more useful, testable, legible and maintainable.