0
$\begingroup$

I am trying to measure complexity of the following code segment

int sum = 0; for (int i = 1; i <= n/2; i++) {    sum++; } 

As far as I understand it can be represented by following sum $\displaystyle\sum_{i=1}^{n/2}1$ but I don't know how to evaluate it.

  • 2
    To measure the complexity of this problem you first have to specify how you want to measure the complexity. It is really important, because the time complexity of this problem can either be $2^{n-1}$ or $O(n)$, depending whether you choose $n$ as the input size, or $\log_{10} n$, the size of $n$ as a string.2011-10-14

5 Answers 5

5

In the sum I guess it's actually $\lfloor n/2 \rfloor$, the largest integer smaller than $n/2$ (basically, if $n$ is odd, throw away the .5 after division by 2), since $n$ isn't always even.

The sum is quick to evaluate:

$\sum_{i=1}^{\lfloor n/2 \rfloor} 1 = \underbrace{1 + 1 + \dots + 1}_{\lfloor n/2 \rfloor \textrm{ terms}} = \lfloor n/2 \rfloor$

  • 0
    Agreed. Changed my wording.2011-03-01
2

Clearly the variable sum will be $\lfloor n/2 \rfloor$ after this code is run. But the OP's code will be less efficient than the code:

int sum=n >> 1; 

This is the right bit-shift of n by 1, i.e. it returns $\lfloor n/2 \rfloor$. Note that many compilers would replace the OP's code with an equivalent of the above. This can be performed in $O(\log n)$ time.

Assuming the OP's code is compiled naively then it performs the following steps:

  • It computes the upper limit $\lfloor n/2 \rfloor$ (the compiler probably converts this to n >> 1). [time complexity: $O(\log n)$]
  • It iterates from $i=1$ to $i=\lfloor n/2 \rfloor$ (requiring $\lfloor n/2 \rfloor-1$ operations "addition by one").
  • At each step, it increments sum (requiring $\lfloor n/2 \rfloor$ operations "addition by one").

[In fact, the OP's code will compute $\lfloor n/2 \rfloor$ three times: once for sum, once for i and once for n/2.]

Now consider the operation "addition by one". Of the numbers $1,2,\ldots,\lfloor n/2 \rfloor$:

  • There are at most $n/4$ numbers whose binary representation ends in 0 (when the operation "addition by one" requires 1 step),
  • There are at most $n/8$ numbers whose binary representation ends in 01 (when the operation "addition by one" requires 2 steps),
  • There are at most $n/16$ numbers whose binary representation ends in 011 (when the operation "addition by one" requires 3 steps),
  • And so on.

Hence, we can expect the average time complexity of the operation "addition by one" to be at most: \[\frac{1}{\lfloor n/2 \rfloor} \sum_{k \geq 1} k \frac{n}{2^{k+1}} = O(1).\]

So we can conclude that the average time complexity is $O(n)$.

1

Since the summation is over a constant value. The answer should be $N/2$ more precisely $(\text{upper limit} - \text{lower limit} + 1) \times \text{constant}$.

Here, $\text{constant} = 1$,$\text{upper limit} = N/2$, $\text{lower limit} = 1$. The $+1$ is because both limits are inclusive.

  • 0
    If $N$ is an odd integer, you need $\text{upper limit} = \lfloor N/2 \rfloor$.2011-10-14
1

If $N$ is a non-negative integer, then \begin{eqnarray} \sum_{i = 1}^{N} 1 = N. \end{eqnarray} In your question, if you mean $\lfloor \frac{n}{2} \rfloor$, which is the greatest integer less than $\frac{n}{2}$, then the sum evaluates to $\lfloor \frac{n}{2} \rfloor$.

  • 0
    @TonyK: Agreed. Edited.2011-02-02
0

It's $O(n)$, because $\lfloor \frac{n}{2} \rfloor \leq \frac{n}{2} = \frac{1}{2} n$.