GATE Overflow | Algorithms | Test 1 | Question: 2

Question

The best known algorithm for binary to decimal conversion runs in $(n$ is the number of bits in the input number, assume MUL and ADD operations to take constant time)

• A. $\Theta(n)$
• B. $\Theta(\log n)$
• C. $\Theta(1)$
• D. $\Theta\left(n^2\right)$

Comments

@Arjun I think answer of this question should be $O(logn)$ as  a decimal number needs max $logn$ bits to be represented in binary, and we need only 1 scan of logn bits to convert a binary number into decimal.

---

See here:

https://cs.stackexchange.com/questions/72204/converting-beta-bit-integer-to-a-decimal-representation-in-thetam-beta

---

I didn't get it from this link sir, could you tell in your own words? @Arjun

Answer 1

we can do in $O(n)$ also..

let given binary no. is of $n$ bits then for each of the bit, we will multiply with $2^i$ ( where $i$ will run from $0$ to $n-1$)

multiplication will take $O(1)$ time, and for each bit, we do this multiply so $\Theta(n)$ is the TC.

Comments

yes, its $\Theta(n)$.

Answer 2

Converting a number from base $b^l$ to $b^k$ takes $O(M(n)logn)$ time, where $M(n)$ is the time it takes to multiply two n-bit numbers, n is the length of the number.

For example, to convert binary to octal (base $2^1$ to $2^3$), the algorithm is easy; group three bits and find their equivalent values paralelly.

---

But to convert from a base to another base where they're not a power of some common constant, the conversion is tricky. For example binary to decimal.

For that, we need to multiply the bit at $ith$ position with $2^{i-1}$

It'll take $O(M(n)n)$ time.

Since $O(M(n)\equiv O(1)$ //given

It takes $O(n) time$

 

Can't be done better than $O(n)$, So, Option A.

---

Intuition

1010011101 to Octal

=> 001 010 011 101

=> 1235

We grouped numbers together, so O(logn)

 

1010011101 to binary requires each digit to be multiplied by some power of 2. So, O(n)