0
$\begingroup$

I'm a little confused with the following problem.

Given two $n$-bit positive numbers $a; b$, compute $a^b$. How many bits does it take to write down the answer, in the asymptotic notation?

I've worked out that the general way to express the number of digits is $bn$; I know that multiplying 2 $n$-digit numbers produces one $2n$-digit number, 3 $n$-digit numbers produce one $3n$-digit number and so on. I'm looking at the problem from the perspective that given the parameters $b$ is simply the number of $n$-bit numbers we want to multiply, with the guarantee that $b$ is also expressed with $n$-bits.

However, is it correct to say that the asymptotic way to express this would be $O(bn)$?

I know that the size of $b$ is not constant since it is guaranteed that $b$ can be expressed with $n$ bits by the problem definition, and I know that for $x>0$ the value of $x$ is always equal to or greater than the number of bits necessary to store it. So intuitively $bn \to n^2$.

Regardless, something just doesn't feel right about saying it would be $O(bn)$ so I'm having a little trouble trusting what I've worked out.

$\endgroup$
1
$\begingroup$

While $O(bn)$ is a correct bound on the length of $a^b$, I think this is not the expected answer. The answer should be in terms of $n$ alone. Since $b=O(2^n)$, the number of digits in $a^b$ is $O(2^nn)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.