427 views

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)

1. $\Theta(n)$
2. $\Theta(\log n)$
3. $\Theta(1)$
4. $\Theta\left(n^2\right)$

@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.

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

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.
by

### 1 comment

edited
yes, its $\Theta(n)$.

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)