Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  sxd Oct 14 '11 at 21:59
add comment

5 Answers

up vote 5 down vote accepted

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$$

share|improve this answer
2  
I am inclined to think that one should say "the sum is quick to evaluate" rather than "easy", because easiness is very subjective. –  Eric Naslund Feb 28 '11 at 18:44
    
I agree with Eric Naslund, the less terms like easy/hard are used the better. Their usage might hinder the mental attitude towards finding solutions. A Simple sum is more descriptive than pointing a sum is easy, it might make the questioner to feel stupid. A complex sum should not be thought as hard but rather as something that should be simplified. I have seen people being discouraged by being told something is hard, rather than being told that something is complicated and it needs somebody to simplify it instead. +1 to @Eric –  Arjang Mar 1 '11 at 1:13
    
Agreed. Changed my wording. –  Calle Mar 1 '11 at 8:42
add comment

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)$.

share|improve this answer
add comment

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$.

share|improve this answer
3  
Because your answer is silly. The function $f$ plays no role. How about: "In general, if n is any integer,..." etc. –  TonyK Feb 2 '11 at 16:38
    
@TonyK: Agreed. Edited. –  user02138 Feb 2 '11 at 20:54
add comment

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.

share|improve this answer
    
If $N$ is an odd integer, you need $\text{upper limit} = \lfloor N/2 \rfloor$. –  Sasha Oct 14 '11 at 21:39
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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