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.
