# Asymptotic Complexity Problems with Subtraction

I know that when finding the asymptotic complexity of a given function, you must pay attention to the rate of change in a for loop. For example:

for (i = 1 to n) { //some action of constant time c; i = i + 4; }

This grows differently than if i simply increased by 1 each time, and so in modeling the runtime of this function, you would not say that it took cn time, but rather say that it took cn/4 time (because the value increased at a rate 4 times faster than usual).

Similarly, if i didn't start at 1 but instead started at a larger value, like i = 7, then this function would be said to take c(n - 7)/4 time.

I sometimes think of it as a staircase with n - i stairs (i to n), and in this case you're climbing it 4 steps at a time (i = i +4) , and you started at the 7th step (i = 7).

What trips me up, however, is when the value is being subtracted. For example:

j = 2n^3; while (j > n) { //some action of constant time c; j = j - 3; }

Here j is not increasing toward n, but rather it is decreasing toward n, and at a different rate. It also has a starting value that is higher than 1 (n is assumed a positive integer).

I interpret this while loop as having a runtime of

c(2n^3 - n)/3

Because the value goes from 2n^3 to n at a rate 3 times faster than is normally expected, and it performs an action of constant time c each time. Or in stairs terms, you're moving across (2n^3 - n) stairs at 3 stairs per step.

Is this a correct interpretation? I know my professor said that addition and subtraction have similar effects here, but something about the subtraction just makes my train of thought turn on its head.

-

Yes. The key is to think of how many times you perform the subtraction. So if you start at $2n^3$, how many times can you subtract $3$ before you get to some value $n$ or less? If you don't mind being out by one then what you have is correct. The answer should also be exactly the same (ignoring out by one errors) as
$j = n$; while ($j< 2n^3$) { //some action of constant time $c$; $j = j + 3$; }