Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

migrated from cstheory.stackexchange.com Oct 17 '12 at 17:54

This question came from our site for theoretical computer scientists and researchers in related fields.

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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.