Why these algorithms have a linear complexity function?

Question

Considering the following algorithms:

int F (int N) {
    int n, i, sum=0;
    for (n=N; n>0; n=n/2)
        for (i=0; i<n; i++)
            sum++;
    return sum;
}

int G (int N) {
    int n, i, sum=0;
    for (i=1; i<=N; i=2*i)
        for (j=0; j<i; j++)
            sum++;
    return sum;
}

Why the number of times sum++ is executed is 2N-1 in both cases? How could I reach this result using summations?

Thanks in advance!

Answer 1

Just try some examples to see why the worst-case complexity is $O(N)$.

For the first code, you have two nested for loops.

• First loop: for i = N downto 1 and for each iteration i the loop halves, i.e., i=N then i=N/2, etc.
• Second loop: for j = 0 to i and you increase j by 1.

So, we have:

1. For i=N, you would need to run the second loop from j=0 to N. This costs, roughly, N iterations. Now, i=N/2.
2. For i=N/2, you would need to run the second loop from j=0 to N/2. This costs, roughly, N/2 iterations. Now, i=N/4.
3. For i=N/4, you would need to run the second loop from j=0 to N/4. This costs, roughly, N/4 iterations. Now, i=N/8.
4. For i=N/8, you would need to run the second loop from j=0 to N/8. This costs, roughly, N/8 iterations.

You would have to do these steps, 1., 2., 3., 4., etc., until $i=1$. It is not hard to see that the number of steps is equal to $\lg N$, since you start with $N$ and you half it each time until you get $1$.

Hence, the number of steps is, roughly, equal to $\lg N$.

Now, how much does each step costs? Well we can easily see that step $i$ costs, roughly, $N/2^{i-1}$ iterations (in the second loop for j). Therefore, the worst-case complexity of the first code is, roughy:

Cost of each step x how many steps which can be calculated as: \begin{align} \underbrace{N+N/2+N/4+N/8+\ldots+1}_{\lg N\text{ times }} &= N\sum_{i=0}^{\lg N}\dfrac{1}{2^i}\\ &\overset{(a)}{=}N\dfrac{1-(1/2)^{\lg N + 1}}{1-1/2}\\ &=2N(1-(1/2)(1/2)^{\lg N})\\ &=N(2-1/N)\\ &=2N-1=O(N), \end{align} where $(a)$ is due to the geometric sum.

Finally, the complexity is $O(N)$ which is linear.

You can prove the same thing for the second code.

Answer 2

Assume for convenience that $N$ is a power of two, i.e. $N=2^k$ for some integer $k$. (This helps since otherwise the first code will do some rounding in the outer loop; but asymptotically this will not change anything.)

• The number of times $\tt sum++$ is called in the first code is $$ \sum_{\ell=0}^{k} \sum_{i=0}^{\frac{N}{2^\ell}-1} 1 = \sum_{\ell=0}^{k} \sum_{i=0}^{2^{k-\ell}-1} 1 = \sum_{\ell=0}^{k} 2^{k-\ell} = \sum_{m=0}^{k} 2^{m} = \frac{2^{k+1}-1}{2-1} = 2^{k+1} - 1 = 2N-1 $$ since for the outer loop we have $i=N,N/2,N/2^2,\dots,N/N$ i.e. $i=N/2^\ell$ for $0\leq \ell\leq k$.

• The number of times $\tt sum++$ is called in the second code is $$ \sum_{\ell=0}^{k} \sum_{j=0}^{2^\ell-1} 1 = \sum_{\ell=0}^{k} 2^\ell = \frac{2^{k+1}-1}{2-1} = 2^{k+1}-1 = 2N-1 $$ since for the outer loop we have $i=2^0,2^1,2^2,\dots,2^k=N$ i.e. $i=2^\ell$ for $0\leq \ell\leq k$.

(In both derivations above was used the formula for a geometric sum: $\sum_{i=a}^b r^i = r^a\cdot\frac{r^{b-a+1}}{r-1}$ (if $r\neq 1$).)