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++;
}
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Have you at least run it? Maybe insert some printfs? Have you wrote it as sum? What is the question anyway? $\endgroup$– EvilMay 18, 2016 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$– hengxinMay 18, 2016 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, 2016 at 9:07
-
$\begingroup$ There are also many examples via algorithm-analysis+loops. $\endgroup$– Raphael ♦May 18, 2016 at 9:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ Better I amend my question: actually wanted to calculate No of time the code c++ run in nested loop. $\endgroup$ May 18, 2016 at 8:40
-
$\begingroup$ better this way I should write code again $\endgroup$ May 18, 2016 at 8:43
-
$\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$– Raphael ♦May 18, 2016 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, 2016 at 9:08