# Need help with this runtime of algorithm with double loops that results in 0

I know with absolute certainty that this is the wrong runtime, but I just wanted to show you how I got to it.

for (i = 0; i <= n; i++) do
j = 2*i
while j <= n do
j = j + 1
print("Hello World")
end


Then I get the runtime
$$Θ(\sum_{i=1}^n 1 + n -2i)=Θ(n+n^2-n(n+1))=Θ(0)$$??

• The runtime of your inner loop isn’t 1+n-2i. It is max (1, 1+n-2i). That’s the fatal mistake in your calculation. – gnasher729 Sep 29 '20 at 8:58
• I follow from $\Theta(\sum_{i=1}^n 1+n)$ to $\Theta(n+n^2)$. How do you get from $\Theta(\sum_{i=1}^n-2i)$ to $\Theta(−n(n+1))$? – greybeard Sep 30 '20 at 6:03

The result you state is clearly wrong, since the second line (for example) runs $$n+1$$ times. The problem is in your sum, which you don't explain how you got to.

Here is the code again, with line numbers:

1: for i in 0,...,n:
2:   j = 2*i
3:   while j ≤ n:
4:     j = j + 1
5:     print "hello world"
6:   end while
7: end for


The running time heavily depends on the model. However, assuming that $$n \geq 0$$, the running time will be proportional to the number of times that lines 2 and 4 are executed. Line 2 is executed $$n+1$$ times. As for line 4, for a given value of $$i$$, it is executed $$\max(n-2i+1,0)$$ times (for example, if $$2i = n$$ it is executed once). In total, it is executed this many times:

$$\sum_{i=0}^n \max(n-2i+1,0).$$ In order to calculate this sum, it will be easier to consider separately the cases $$n$$ even and $$n$$ odd. If $$n = 2m$$ then the maximal $$i$$ for which $$n-2i+1>0$$ is $$m$$. Furthermore, the summand goes from $$n+1$$ down to $$1$$ in jumps of $$2$$; there are $$m+1=n/2+1$$ summands in total. Therefore the sum equals $$1 + 3 + 5 + \cdots + (n + 1) = \frac{(n/2+1)(1+(n+1))}{2} = \frac{(n+2)^2}{4} = \Theta(n^2).$$ If $$n = 2m+1$$ then the maximal $$i$$ for which $$n-2i+1>0$$ is also $$m$$. This time, the summand goes from $$n+1$$ down to $$2$$, and there are $$m+1 = (n+1)/2$$ summands. Therefore the sum equals $$2 + 4 + 6 + \cdots + (n+1) = \frac{((n+1)/2)(2+(n+1))}{2} = \frac{(n+1)(n+3)}{4} = \Theta(n^2).$$ In total, we get that the number of times that line 4 is executed is $$\Theta(n^2)$$ in both cases, and so $$\Theta(n^2)$$ overall (this is a subtle point, and requires a short argument).

We conclude that the total running time is $$\Theta(n^2)$$. (This may need the assumption $$n>0$$, depending on your exact definition; you can take $$\Theta(n^2+1)$$ if you want to be extra sure.)

Sum $$\sum_{i=1}^n (1 + n -2i)$$ is wrong calculation, because while loop produce steps only when $$2i \leqslant n$$.

• So it's $\sum_{i=1}^n n -2i$? But don't I need to add the runtime $Θ(1)$ it takes to run each step for the while loop? – Jacob Toho Sep 29 '20 at 7:59
• If you count each line (not operation), then you'll have only $2$ working lines inside for loop after $n-2i<0$. $1$ assignment and $1$ checking while condition. – zkutch Sep 29 '20 at 8:24
• Jacob, it's not n - 2i. When i = n, it doesn't take minus n steps to perform the loop, it takes one step, which is an awful lot more than minus n. – gnasher729 Sep 29 '20 at 10:28