Time complexity for loops

Question

I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated.

int j = 1; int n = any;

    while( j < n){
        int k = j;
        while(k < n) {
            if (k % 2 == 1) {
                k++;
            } else {
                k += 0.01 * n;
            }
        }
        j += 0.1 * n;
    }

I think it's O(1) because outer loop executes 10 times and inner loop can vary but it's or +1 or 10 times too. But after a +1 it advances n/10. And after it advances n/10 it can advances n/10 or +1.

Answer 1

Note that the increments 0.01 * n and 0.1 * n will actually evaluate to $\lfloor \frac n{100}\rfloor$ and $\lfloor \frac n{10}\rfloor$ - except that we may have rounding errors from float to int conversion; but then again we must allow unbounded values for the int type (or we can say the complexity is vacuously $O(1)$), so why not assume infinite precision for the float type? At any rate, $\lfloor \frac n{100}\rfloor>\frac n{100}-1>\frac n{200}$ if $n>200$. Hence for such $n$ the inner loop will advance $k$ by more than $\frac n{200}$ in any two consecutive rounds (because the first if branch acnnot be taken twice in a row); therefore it will loop at most 200 times. Liekwise, for $n>200$ we have $\lfloor \frac n{10}\rfloor >\frac n{10}-1>\frac n{10}-\frac n{200}=\frac{19}{200}n $ and hence the outer loop will loop at most 22 times. Therefore we obtain a constant bound for the running time for all $n>200$. Complexity is therefore $O(1)$ (and vacously also $\Omega(1)$ and so $\Theta(1)$).

Note that for $2<n<100$, the inner loop may fail to terminate at all. Likewise, for $2\le n<10$ the outer loop may not terminate.