# Halving – Intro to Algorithms

The fact that the number of statements that it takes to execute naive(a, b) is a linear function of a shouldn’t come as a surprise to us at this point. We actually plotted the running time, and it really did give a very nice linear function. Russian is going to be a bit trickier for a couple reasons. One, is it seems much more obscure how many times it’s going to go through this loop. It seems like some of the statements are actually conditioned on properties that we don’t necessarily know as a simple function of the inputs. The plot that we made was basically useless. It just seemed like the time was more or less constant. It’s not actually constant, and we can actually work out a function of what it is. The key step in analyzing the number of steps that this algorithm is going to take is understanding how many times this loop is going to be executed. The number of times the loop is going to be executed is going to be the same as the number of times that it takes to divide x in half before you get down to 0. This is, again, a half and rounding down. How man times can you divide x in half rounding down before you get down to 0? An important thing you need to know is how many times can you divide a number x in half, rounding down, before it hits 0? Here are some examples. If x can be something between 0 and 11, here’s how many halvings. If the number if 0, then you don’t have to halve it at all to get down to 0. If it’s 1, you have to halve it once. If it’s 2, you have to halve it twice–once to get you down to 1 and then once more to get to 0. It looks like it’s a linear function so far, but actually it diverges now. The number 3 you have to halve it once to get down to 1 and then once more. Four you have to do three times–once to get it to 2, then 1, then 0. It stays that way until you get the 8, which takes 4 times–once to get it to 4, 2, 1, 0. It stays 4 for a while and the next time it changes is at 16. Which of these functions captures the relationship between x and the number of times x needs to be halved to get down to 0. Just to simplify things a bit, let’s get rid of the 0 case, because it’s a bit messy. The functions are x–seems to work for a little while– x/2, the log base 2 of x, and the log base 2 of x floor–meaning rounded down if it’s not an integer–plus 1.