# 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++;
}


## marked as duplicate by Raphael♦May 18 '16 at 9:07

• Have you at least run it? Maybe insert some printfs? Have you wrote it as sum? What is the question anyway? – Evil May 18 '16 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. – hengxin May 18 '16 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. – Raphael May 18 '16 at 9:07
• There are also many examples via algorithm-analysis+loops. – Raphael May 18 '16 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. – Rizwan Ahmed May 18 '16 at 8:40
• better this way I should write code again – Rizwan Ahmed May 18 '16 at 8:43
• Please consider not to encourage undesirable posting behaviour. – Raphael May 18 '16 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. – Raphael May 18 '16 at 9:08