posted 2 months ago
Oops... I completely screwed up, missed the 'i = i * i' and 'j = j * j'. Sorry for that!
Well, that change makes it somewhat harder. What I do in these cases is calculating both methods for several different input values, list the output and try to see some connection between the input and output. I used, as input, the values 2, 4, 8, 16, ... up to 2^100 (be careful, use BigIntegers). You see first that, after a certain input value, that the second method is calculated more than the first method. For instance, when n = 2 ^51, the first method is calculated 21 times, the second 51 times. The second method has O(2log(n)) = O(ln(n)), the first is more complicated, you get that 2 ^(2 ^n) gives a count of 1 + 2 + ... + (n + 1), with a floor function for intermediate values.