title: Time and space complexity of base conversion code
body: <p>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.</p>
  
  <p>My code is:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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.</p>
  
  <p>I know everything is constant before <code>for digit in num_as_string[::-1]:</code>. In this loop, it's just `O(n) where n is just number of digits of the input. </p>
  
  <p>Then in <code>while base10 &gt; 0</code>, it runs the look while <code>base10</code> becomes 0. So, this would be something like <code>O(number of digits in base10)</code></p>
  
  <p>Finally, on <code>for i in converted[::-1]</code>, this would also be <code>O(number of digits in base10)</code>.</p>
  
  <p>So, I am assuming the time complexity of this code is something like <code>O(n) + 2 * O(number of digits in base10)</code> which is linear.</p>
  
  <p>For space, I am assuming it's <code>O(number of digits in base10)</code> because I store it in <code>converted</code> list. </p>
  
  <p>Are my observations correct? If not, what am I missing? Also, can this code be improved in terms of time and space complexity?</p>
  
  <p>Thanks</p>