What's the time complexity (big-O) of two nested for loops with the same length that increment doubling the iterator variable?

Question

Like this:
for i=1; i to n; i=i+i:
for j=1; j to n; j=j+j:
//do stuff

Answer 1

I believe it would be closer to O(n(^1/2*2))
= O(n)

Square root because of how the itteration works. Times 2 because there's another loop. Could be wrong though.
Perhaps compare the computation speed with an O(n) loop, and see how close they were.

Answer 2

I compared it in my computation speed comparer code. Can confirm it's close to O(n).

Answer 3

Actually it cannot be O(n**2). It has to be much smaller as the variables only iterate over powers of two and powers of two get exponentially scarcer as n grows.

Answer 4

O(n^2)

Answer 5

Ah... ok. Then it is (probably):

O(log(i*j))

Answer 6

I think we need a formula that returns the number of powers below a given threshold n. Then we could multiply that by itself.
Whether that's log or sqrt I don't have the know-how to determine.

Answer 7

shouldn't it depended on I and j, instead of n?

Answer 8

No, because i and j are fixed; they're always incremented by their own value. Only n grows assimptocally.

Answer 9

Rrestoring faith, good work.