run time analysis of a for loop
In your loop, $j$ will take the values $1, 2, 4, 8, \dotsc, 2^k$ where $2^k&lt;n$. You need to know how many times this will iterate. In other words, what will be the largest $k$ for which we have $2^k &lt; n$? Take the log to the base 2 of each side of the inequality and you're asking what the largest $k$ will be for which $k&lt;\log_2n$. What this means is that you're right in your comment: the loop will iterate no more than $\log_2n$ times.