Time: :

2^{r-1}, 2^{r-2},...,2^{3},2^{2}, 2^{1} where r is the order* of 2 mod n =

Given the following relation:

a_{1} = (n+1)/2 given an odd n

a_{i} = a_{i-1}/2 if a_{i-1} is even

a_{i} = (a_{i-1}-1)/2 + a_{1} if a_{i-1} is odd

* The order of 2 mod n is the smallest integer r such that 2^{r} = 1 mod n