[Solved]: Analysis of very simple algorithm

Problem Detail: 

I need to find the time complexity of the following simple algorithm.

Calculate the time complexity of the following algorithm:

void f(int n) {   int i, x;    for (i = 1; i <= n; i++)     if (i % 2 == 1)       x++ } 

It obvious that the time complexity of this algorithm is $\Theta(N)$, but how I prove it formally?

I know that the loop will do $N$ iterations, so the total number of operations will be $N \times \text{(number of operations inside the loop)}$.

Here the tricky part, I know that for each iteration will be one operation for the comparison and one operation only if $i$ is odd.

So it's something like this: $\sum_{i=1}^{n}(1+\frac{1}{2})$? I'm not sure, it's seems too strange and I'm not sure how to continue.

What is the best way to write it formally?

Also, I would like to ask if there are books with many examples of analysis of simple algorithms like this and proofs of their complexity. The most recommended book seems to be CLRS, but I didn't found many examples of this kind there and from what I understand it can be very complex topic (depending on the series you need to calculate in the end).

Thank you.

Asked By : EMDB1

Answered By : Eli Rose

You're doing the right thing. There's no magic that you're missing.

$$ \begin{aligned} \sum_{i=1}^n (1 + \frac{1}{2}) &=\\ &= \sum_{i=1}^n \frac{3}{2}\\ &= \underbrace{\frac{3}{2} + \dots + \frac{3}{2}}_{n \text{ times}}\\ &= \frac{3}{2}n \in O(n) \end{aligned} $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40369