counts iteration in a nest for-loop <p>Here is the pseudo code:</p> <pre><code>for i=1 to n for j=1 to n for k=1 to j x = x+1 </code></pre> <p>and I have to calculate these two thing (i) count it precisely (ii) find it big-O</p> <p>in (i), my final answer is n^4+2n^3+5n^2+4n+2. in (ii), because there are three loop, so it's O(n^3);</p> <p>It seem that there must be an error either (i) or (ii) since (i) raise to the power 4, and the big-O is just 3.</p> <p>Here is my step when counting the iteration:</p> <pre><code>for(i=1; i &lt;=n; i++) </code></pre> <p>count as 1+(n+1)+n which is (2n+2).</p> <p>So, (2n+2)+n(2n+2)+n(4+6+8+...+2n+2)+n^2(1+2+3+...+n)(2) which finally come out with n^4(see the last term, sum of AS * n).</p>