1
$\begingroup$

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)$??

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Sep 29 '20 at 8:58
  • $\begingroup$ 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))$? $\endgroup$ – greybeard Sep 30 '20 at 6:03
1
$\begingroup$

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.)

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Jacob Toho Sep 29 '20 at 7:59
  • $\begingroup$ 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. $\endgroup$ – zkutch Sep 29 '20 at 8:24
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Sep 29 '20 at 10:28

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.