Gate 2018

Question

for(i=1; i<=n; i++) {

      for(j=i; j<=n; j++){

         for(k=j+1; k<=n; k++){

               printf("Hello"); } } }

How many times print statement is executed for n=4 and what is the time complexity?

Comments

10 times for n=4

complexity will be $\sum \frac{r(r+1)}{2}$ = O(n³)

---

Thank you..I got it

---

$= \sum_{i=1}^{n}\sum_{j=i}^{n}\sum_{k=j+1}^{n} 1 \\ = \sum_{i=1}^{n}\sum_{j=i}^{n}(n-j) \\ = \sum_{i=1}^{n}(n-i) + (n-(i+1)) + .....+ (n-n)\\ =\frac{1}{2}\sum_{i=1}^{n}(n-i)(n-i+1) \\ =\frac{1}{2}\sum_{i=1}^{n}(n^{2} +n+i^{2}-(2n+1)i)\\ = \frac{1}{2} \left( n^3 + n^2 + \sum_{i=1}^{n}i^2 - (2n+1). \sum_{i=1}^{n} i \right)\\ =    \frac{1}{2} \left( n^3 + n^2 + \frac{n. (n+1). (2n+1)}{6} - (2n+1). \frac{n. (n+1)}{2} \right) \\ = \frac{1}{2} \left( n^3 + n^2  - \frac{n. (n+1). (2n+1)}{3} \right) \\ =  \frac{n}{6} \left( 3n(n+1)   -  (n+1). (2n+1) \right) \\= \frac{n. (n+1)}{6} (n-1) \\ =\frac{(n-1)n(n+1)}{6}$

---

can you show the solution  joshi_nitish.