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$; }

if that helps.

  • $\begingroup$ Thank you, that helped me a great deal. $\endgroup$ – Chris Jan 21 '13 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.