Discussion about Base Conversion (5.3)

#1

I have couple points to discuss about Base conversion(5.3):

  1. Intermediate base conversion
  2. Complexity
  3. Negative number representation

1.intermediate base conversion
Even though, its not mentioned anywhere explicitly, the formula for generalization in terms of summation, given in the book for is actually converting a number in b1 to number in base 10.
e.g s = “314”, b1 = 5
then x = 97, is actually in “314” represented in base 10 (if b2=10 our answer would indeed be 97)

So, the solution given in book can also be termed as:

  1. convert a number in b1 to base 10(x)
  2. convert x to a number representation in b2
    Just confirming my understanding as it’s nowhere mentioned explicitly

2.Complexity:
I had tried to solve 5.3 on my own and the solution I came up with is pretty much similar to what’s given in the book. I derived that the complexity of my (and book’s) solution is O(max(n,p)),
n: number of bits needed to represent x in base b1(n = log_b1_(x))
p: number of bits needed to represent x in base b2(n = log_b2_(x))
please note that log_b1_(x) means log(x) to the base b1

I also understand the explanation given for complexity in the book. But, by the rules of Big-Oh notation O(a+b) is governed by higher order term.
If we look at the book’s solution, O(n(1+log_b2_(b1))), the term log_b2_(b1) will either be:
a constant>1… if b1>b2 or
a constant between 0 to1 if b1<b2
In any case, the complexity still going to be O(n)

So shouldn’t the complexity be O(n)?

3.Negative number representation:
in the solution, the negative numbers are represented by appending “-” as a prefix.
But, some bases, e.g. binary, use special representation(1’s and 2’s complement).
I know this is specific to the computers and not to the base 2 per say.

But I thought, may be as interviewee we should at least mention this? Any thoughts?

0 Likes
#2

Hey @joshash1102,

Thanks for your question. Following is my reply:

  1. You are right about the idea that we convert from b1 to base 10 first, and then convert to b2.
  2. The complexity part is also correct and you can treat it as O(n).
  3. I think you can extend the 2’s complement idea here to other base. Just remembering that the reason why 2’s complement for (i.e., for fast subtraction). Anyways, here we just use simple representation for this problem.
0 Likes