0
$\begingroup$

First of all, I know there are many questions like this on the site. But I think this case is a bit different.

Consider the following code:

int i, j, k;

for (i = 1; i <= n; i++){   
    for (j = 1; j <= (n-i); j++) {
        System.out.print(" ");
    }

    for (k = 1; k <= (i-j); k++) {
        System.out.print(i);
    }

    System.out.println();
}

What would be the time complexity of this code? It seems like O(n^2) to me but I can't justify it properly.

How our professor told us to compute complexity is just by adding all the summations together from every line.

$$ (n+1) + \sum_{j=1}^{N-i} + \sum_{j=1}^{N-i} + \sum_{k=1}^{i-j} + \sum_{k=1}^{i-j} + n $$

However, I've never seen examples with summations like $\sum_{j=1}^{N-i}$, It's always either $\sum_{j=1}^{N-1}$ or some constant number being subtracted from N, which is easier to sum. So, How would I solve this? And is it O(n^2)?

$\endgroup$
5
  • 1
    $\begingroup$ There are two parts here. 1) Derive the correct sums. "Adding all the summations together" is vague; nested loops lead to nested sums. See here. What you wrote down there doesn't make much sense; what's $\sum + \sum$? How do you get four sums from three loops? 2) Simplify the sums. They are particularly easy here, especially with a formulary at hand (e.g. the TCS Cheat Sheet). For help on simplifying sums, please hit Mathematics. $\endgroup$
    – Raphael
    Mar 9, 2019 at 12:45
  • 1
    $\begingroup$ Community votes, please: Seems like a duplicate of our reference question to me. $\endgroup$
    – Raphael
    Mar 9, 2019 at 12:47
  • $\begingroup$ Hint for the sums: Sometimes reversing the order of summation can lead to an easily recognized form. $\endgroup$
    – Raphael
    Mar 9, 2019 at 12:47
  • $\begingroup$ Are you sure that your professor wrote this ? $\endgroup$
    – user16034
    Sep 7, 2022 at 10:10
  • $\begingroup$ I suspect that you also incorrectly copied the code, because the presence of j in the third for loop is unexpected. $\endgroup$
    – user16034
    Sep 7, 2022 at 10:12

3 Answers 3

0
$\begingroup$

The number of print statements executed is $$ \sum_{i=1}^n \left[ \left(\sum_{j=1}^{n-i} 1\right) + \left(\sum_{k=1}^{i-(n-i+1)} 1\right) + 1 \right], $$ where the second sum is zero if $1 > i-(n-i+1)$.

The running time is proportional to the number of print statements, so it remains to compute the value of the expression above, or at least to give a good estimate. This I leave to you.

$\endgroup$
3
  • $\begingroup$ When I submitted the assignment, I got a equation very close to your equation there, Exactly, It was $\sum_{i=1}^n \left[ \left(\sum_{j=1}^{n-i} 1\right) + \left(\sum_{k=1}^{i-(n-i)} 1\right)\right]$ and I solved it to $n(n+1)/2$ Which seems perfect to me but I still got 3/10 on it. $\endgroup$
    – candh
    Mar 9, 2019 at 13:57
  • $\begingroup$ What he wants is a "line by line analysis" which I don't really understand how to perform. That's why the confused/non-sensical equation in the question. The most ridiculous thing was when he tried to explain that the second inner loop never runs, given any value of n, i, or j afterwards in the class. $\endgroup$
    – candh
    Mar 9, 2019 at 14:00
  • $\begingroup$ You'll have to ask your professor for what he means by "line by line analysis". As for your solution, I'm not 100% sure it's correct, though the expression is certainly $\Theta(n^2)$. $\endgroup$ Mar 9, 2019 at 14:22
0
$\begingroup$

For better analysis the code, you can rewrite loop that use variable $k$ in terms of $n,i$ not $j$:

  int i, j, k;
    
    for (i = 1; i <= n; i++){   
        for (j = 1; j <= (n-i); j++) {
            System.out.print(" ");
        }
    
        for (k = 1; k <= (i-(n-i+1)); k++) {
            System.out.print(i);
        }
    
        System.out.println();
    }

Let $T(n)$ be time complexity of code. Therefore our code have two disjoint inner loop that displayed by the following summation (suppose each operation System.out.print need constant time, notice that, the inner loop with variable $j$ has the cost $(n-1)+(n-2)+\dots+1=\sum_{i=1}^{n-1}i$), so:

$$T(n)=\sum_{i=1}^{n-1}i+\sum_{i=1}^{n}\left(\sum_{k=1}^{i-n+i-1}\mathcal{O}(1)\right)$$ $$=\sum_{i=1}^{n-1}i+\sum_{i=1}^{n}\left(\sum_{k=1}^{2i-n-1}\mathcal{O}(1)\right)$$ $$=\sum_{i=1}^{n-1}i+\sum_{i=1}^{n}(2i-n-1)=\Theta(n^2)+\mathcal{O}(n^2)$$ $$=\Theta(n^2)$$

$\endgroup$
0
$\begingroup$

Let us work out an example with $n=5$.

The outer loop is executed with $i=1,2,3,4,5$. Thus the first inner loop executes $4+3+2+1+0$ print's. And the second inner loop $0+0+0+2+4$ print's.

For $n=6$, we have $5+4+3+2+1+0$ print's. And the second inner loop $0+0+0+1+3+5$ print's.

We can easily generalize and get the counts $n$ (outer), $\dfrac{(n-1)n}2$ (first inner) and $\dfrac{n^2-1}4$ or $\dfrac{n^2}4$ depending on the parity of $n$ (second inner).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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