-2
$\begingroup$

This question already has an answer here:

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++;
}
$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Have you at least run it? Maybe insert some printfs? Have you wrote it as sum? What is the question anyway? $\endgroup$ – Evil May 18 '16 at 6:40
  • $\begingroup$ 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. $\endgroup$ – hengxin May 18 '16 at 7:21
  • $\begingroup$ 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. $\endgroup$ – Raphael May 18 '16 at 9:07
  • $\begingroup$ There are also many examples via algorithm-analysis+loops. $\endgroup$ – Raphael May 18 '16 at 9:08
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Better I amend my question: actually wanted to calculate No of time the code c++ run in nested loop. $\endgroup$ – Rizwan Ahmed May 18 '16 at 8:40
  • $\begingroup$ better this way I should write code again $\endgroup$ – Rizwan Ahmed May 18 '16 at 8:43
  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael May 18 '16 at 9:07
  • $\begingroup$ 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. $\endgroup$ – Raphael May 18 '16 at 9:08

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