0

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.

DPenner1
  • 192
John
  • 1
  • 2

1 Answers1

1

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)$.

40 votes
  • 9,736