# What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)? [duplicate]

I am looking for the time complexity of the following nested loops, where the inner loop is shrinking.

function(int n){
c=0;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
c++;
}
• Have you at least run it? Maybe insert some printfs? Have you wrote it as sum? What is the question anyway?
– Evil
May 18, 2016 at 6:40
• Welcome to Computer Science! Your question is a very basic one. Please show your attempts to solve it on your own. Also please see one of our reference questions. May 18, 2016 at 7:21
• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. May 18, 2016 at 9:07
• There are also many examples via algorithm-analysis+loops. May 18, 2016 at 9:08

It's not hard to see how many times c gets incremented. Each $+$ in the table below represents one c++ operation.

$$\begin{array}{r|ccccccc} &i=1&2&3&4&5&6&\cdots&n \\ \hline \\ j=1& +&+&+&+&+&+&\cdots&+& \\ 2& &+&+&+&+&+&\cdots&+& \\ 3& & &+&+&+&+&\cdots&+& \\ 4& & & &+&+&+&\cdots&+& \\ 5& & & & &+&+&\cdots&+& \\ 6& & & & & &+&\cdots&+& \\ \vdots& & & & & & &\ddots&+& \\ n& & & & & & & &+& \\ \end{array}$$

The total number of $+$ operations is

\begin{align} 1 + 2 + 3 + \cdots + n =&\ \frac{n (n + 1)}{2} \\ =&\ \frac{n^2}{2} + \frac{n}{2} \end{align}

… which is roughly $\dfrac{n^2}{2}$, which is usually just characterized as $O(n^2)$. You can also see that roughly half of the $n \times n$ square is filled in.

• Better I amend my question: actually wanted to calculate No of time the code c++ run in nested loop. May 18, 2016 at 8:40
• better this way I should write code again May 18, 2016 at 8:43
• Please consider not to encourage undesirable posting behaviour. May 18, 2016 at 9:07
• Since you do not count all operations, you need to be careful with your conclusions. Also, $O(n^2)$ is weaker than what you prove; you actually show that there are $\Theta(n^2)$ incrementations of c. May 18, 2016 at 9:08