Where did I go wrong with this algorithm analysis? I was asked to calculate k.

Question

The question says that $x$ and $y$ are in the form of $2^P$. So I assumed that meant:
$x =$ $2^{p_1}$;
$y =$ $2^{p_2}$;

i = 1;
j = y;
k = 0;

while (i < x) { //1.
  i = i * 2; // 2.
  k = k+1; // 3.
}
//4.

while (j > 1) { // 5.
  j = j / 2; // 6.
  k = k + j; // 7.
}

This is my attempt:

1. Loop runs from $1$ to $2^{p_1} - 1$.
2. Loop increments $2^{p_1}/2$ times.
3. $k$ becomes however many steps the loop takes.
4. Therefore, $k$ becomes $\sum_{i=1}^{(2^{p_1} - 1)/2}k $
5. Loop runs from $2^{p_2}$ to $1 + 1$.
6. Loop increments $2^{p_2}/2$ times.
7. $k$ becomes $\sum_{i=1}^{(2^{p_1} - 1)/2}k + \sum_{i=1}^{(2^{p_2} - 1)/2}k $

So the answer I got is: $\sum_{i=1}^{(2^{p_1} - 1)/2}k + \sum_{i=1}^{(2^{p_2} - 1)/2}k $.

The answer is actually $\sum_{i=0}^{logx - 1}2^{i+1} + \sum_{j=0}^{logy - 1}2^{j+1}$. I'm fairly lost at how to arrive at this answer, any help would be appreciated.

Answer 1

$i$ will run through the powers of $2$ upwards, entering the while loop's body from $i=2^0$ to $i=2^{p_1-1}$ inclusive, so $k$ is incremented $p_1$ times.

$j$ will run through the powers of $2$ downwards, entering the while loop's body from $j=2^{p_2}$ to $j=2^1$ inclusive. Half of the value $j$ had at loop start is added to $k$, i.e. $\sum_{z=0}^{p_2-1}2^z$ in total.

So at the end $k=p_1+2^{p_2}-1=\log x+y-1$.