0

I'm trying to solve a problem in which I look at a fragment of pseudocode and try to develop summations from it so I can analyze the time complexity of the overall loop. The code is this:

for i=1 to n:
    for j=1 to n:
        if n<(n+i)/2:
             for k=1 to n

I know that the third loop only executes when the 'if' statement holds true. However, if I plug in a value 'i' starting at 1, I see that, even if $n=1$, there is no possible way that the third loop could ever execute since if $i=1$ and $n=1$, then $1<\frac{1+1}{2}$ is not valid, and this seems to be the smallest possible example. So therefore I would think that the final set of summations would look like this:

$\sum_{i=1}^n\sum_{j=1}^n$

Am I missing something or is this valid?

bpryan
  • 65
  • 1
  • 7

1 Answers1

0

$$n < \frac{n+i}2$$ is equivalent to

$$i > n$$

but $i$ is defined to be at most $n$. Hence you are right that the third loops doesn't run and we end up with $O(n^2)$.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149