# Runtime analysis of a nested loop

I have some difficulties performing the worst case analysis on this algorithm.
The outermost loop is executed $2N$ times.
The while loop, in the worst case, will increase by $2$ each time, so it performs $i/2$ basic operations ($*2$ because double call)

for (i=1; i<=2*N; i++) {
j = 0;
while (j <= i) {
a[i] = function (function (a[i]));
if (c[i][j] != 0)
j = j + 6;
else
j = j + 2;
}
}


function is the basic operation.
Am I going the right way?

• You say you have difficulties. What are they, specifically? – Raphael Oct 17 '12 at 20:05
• what is function() ? what is c[][] ? – AJed Oct 17 '12 at 22:50

The worst case for the number of function calls is (as you already observed)

$$\sum_{i=1}^{2N}\sum_{j=1}^{i/2} 2 =\sum_{i=1}^{2N} i = \frac{2N(2N+1)}{2}=2N^2+N,$$

by Gauß' summation formula.

Let $f(N)$ denote the number of function calls within the loop.

Substituting $N+1$ instead of $N$ into the code you can observe that the first $2N$ iterations of the outer loop remain exactly the same and the last two iterations add up to $N+1$ and $N+2$ iterations of the inner loop each. Since each iteration of the inner loop results in two function calls, you can arrive to the following estimation $$f(N+1) \leq f(N) + 4 N + 6$$

Observe also that $$f(1) \leq 6$$

Starting from here you can obtain an upper bound $F(N)$ for $f(N)$ by solving the recurrence $$\begin{eqnarray*} &&F(N+1) = F(N) + 4 N + 6\\ &&F(1) = 6 \end{eqnarray*}$$

The solution for this recurrence is a function quadratic in $N$. I will add the exact solution later.