edited by
733 views
3 votes
3 votes

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)$
edited by

2 Answers

Best answer
12 votes
12 votes
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.
edited by
1 votes
1 votes

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)

Answer:

Related questions

2 votes
2 votes
1 answer
2
Bikram asked Oct 4, 2016
329 views
The Matrix Chain-Product dynamic programming Algorithm runs in _______linear timeexponential timequadratic timecubic time
3 votes
3 votes
1 answer
4
Bikram asked Oct 4, 2016
502 views
Let we have 3 steps of an arbitrary program fragment whose running times are $O(n^2), \: O(n^3)$ and $O(n\log n)$, then the running time of whole program is$O(n^3)$$\Omeg...