Here is a multiplication algorithm: given inputs x and y, add x to itself y – 1 times:
z = 0
while y > 0:
z = z + x
y = y – 1
return z
What is the running time of this algorithm? Is it polynomial or exponential?
SOLUTION
Suppose x and y are n bits long. Then all the intermediate numbers generated, up to the final answer xy, are O(n) bits long. Each iteration of the loop involves addition and subtraction of O(n)-bit numbers, and therefore takes O(n) time.
The loop iterates y = O($2^n$) times. Therefore the overall running time is O($n2^n$), exponential.
i am confused as to how the came up with that answer, can someone please walk me through this problem.
Best Answer
Suppose that $x$ and $y$ are $n$ bits long. Then $x+x=2x$ is at most $n+1$ bits long, $2x+x=3x$ is at most $n+2$ bits long, and in general $kx$ is at most $n+k-1$ bits long. In particular, $xy$ is at most $n+n-1=2n-1$ bits long. The values of $z$ generated by this algorithm are the numbers $kx$ for $k=0,1,\ldots,y$, and we’ve just seen that they all have fewer than $2n$ bits. Addition and subtraction of two numbers of at most $2n$ bits takes at most $2kn$ time for some positive constant $k$, so each iteration of the loop takes at most $2kn$ time.
We go through the loop $y$ times. The largest $n$-bit number is $2^n-1$, so we go through the loop fewer than $2^n$ times, and the total time is therefore bounded above by $2kn\cdot2^n$. That is, if $t(x,y)$ is the time required for inputs of $x$ and $y$, we have $t(x,y)<2kn\cdot2^n$. It follows that if $T(n)$ is the maximum running time over all inputs $\langle x,y\rangle$ such that $x$ and $y$ are both at most $n$ bits long, then $0\le T(n)<2kn\cdot2^n$ for all $n\in\Bbb Z^+$. Since $2k$ is a fixed positive constant, this means precisely that $T(n)$ is $O(n2^n)$, which is exponenetial, not polynomial.
Note: I’ve neglected overhead: some time is spent in initialization and output. That overhead is essentially constant, however, so $T(n)$ is bounded by $c+2kn\cdot2^n$ for some constant $c$, and since $n2^n$ is unbounded, it’s not hard to verify that $c+2kn\cdot2^n$ is also $O(n2^n)$. This is routine, which is why it isn’t even mentioned in the solution that you have.