2 ms·
> Best case, say we lie on a number of the form 2^2r, e.g. 64. > We travel 1, -2, +4, ... , -32, 64. > We've travelled 127 steps. I think it's 190 = 64+2*(2^
by kgwgk 12y ago
> Best case, say we lie on a number of the form 2^2r, e.g. 64.
> We travel 1, -2, +4, ... , -32, 64.
> We've travelled 127 steps.
I think it's 190 = 64+2*(2^0+2^1+2^2+2^3+2^4+2^5) = 64+2+4+8+16+32+64
> Overall this takes method travels approximately between 2n and 8n.
I think asymptotically the range is [3n,9n]