The Ethiopian multiplication algorithm is a way of finding the product of two numbers without using multiplication. Let's say we want to multiply 35 by 88. The algorithm goes like this
\begin{array}{rr|r} & 35 & 88 \\ & 17 & 176 \\ & [8] & [352] \\ & [4] & [704] \\ & [2] & [1408] \\ & 1 & 2816 \\ & & \\ \hline & & 3080 \\ \end{array} We list the numbers in two columns and we divide the first by 2 at each step until we reach 1 and multiply the other by 2 at each step. Then we sum down the second column ignoring those which has a corresponding even number from the first column. so $3080=88+176+2816$. How do we calculate the running time of this algorithm?