"$x=2x$" has nothing to do in your running-time -- it is something the function does, and doesn't say how long it takes to do it.
If we suppose that multiplication and assignments both take constant time, each execution of x=2x will take some fixed time $t_0$. So you need to figure out how many times that is executed. $23$ is not the answer here -- the doubling happens 23 times each time the body of the b loop runs!
If you don't worry about fancy notation for the moment, how would you compute the number of executions of x=2x for some concrete value of $n$ -- for example, $n=64$?
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.
Best Answer
The first inner loop (the one based on
for b = 1 to n) usesnsteps. Thennis replaced bysqrt(n)hence the second inner loop usessqrt(n)steps, and so on. This shows the run time isn + sqrt(n) + sqrt(sqrt(n)) + ...If
n = 2^(2^k)thensqrt(n) = 2^(2^(k-1)),sqrt(sqrt(n)) = 2^(2^(k-2)), and so on, hence there arekterms in the sum above. Thus, for some generaln, there are aboutlog(log(n))terms. Counting the first loop separately, one sees that the run time is more thannand less thann + sqrt(n) * log(log(n)). Finally, the run time is equivalent ton, in particular it isΘ(n).