Runtime analysis of a nested loop

Question

I have some difficulties performing the worst case analysis on this algorithm.
The outermost loop is executed 2ドルN$ 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?

• Raphael: You say you have difficulties. What are they, specifically?
• AJed: what is function() ? what is c[][] ?

Answer 1

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.

Answer 2

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 2ドルN$ 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.