Number of Comparisions (II)

Computer Science Level 2

Find the number of comparisons done in the following algorithm.

a := 0
for i := 0 to i := n
    if (i mod 2) = 1
        a := a + 2
    else
        a := a + 1
print a

Assumptions and Details

$n$ is a non-negative integer.
Don't count any comparison made by the for loop itself (i.e. whether or not to proceed with another loop).

Can you solve this as well?

2n

n+1

2n+2

n

2 solutions

Zeeshan Ali
Dec 22, 2015

For any non-negative integer n, the for-loop runs (n+1) times where there is an if-else comparison. Hence the total number of comparisons done are $\boxed {n+1}$ .

What about the n+1 comparisons happening in for loop's control code (Is I between 0 and n)? Shouldn't it be total of 2n+2?

Ramesh Jayaraman - 5 years, 5 months ago

No, i is from 0 to n.. Hence for-loop runs n+1 times. More over each time there is only a single comparison done which is either i mod 2 is 1 or 0 .

Zeeshan Ali - 5 years, 5 months ago

I cannot agree - every iteration of the loop the code checks if counter exceeds n or not hence additional n+1 comparisons in the loop header.

Stas Lisniak - 5 years, 5 months ago

@Stas Lisniak – Ah, I was wrong - half of the times comparison happens in the for loop and other half in the if statement. Nice problem! :)

Stas Lisniak - 5 years, 5 months ago

@Stas Lisniak – Not really. I think you're correct. I answered $(n+1)$ without considering the condition checking in the for loop. Note that it is a which is incremented by 2 or 1 according as i is odd or not. i itself is incremented normally by 1 without any condition checking at the end of the for loop block.

So, I think you're correct in your assessment that there are $(2n+2)$ comparisons since i goes through all non-negative integers $\leq n$ with two comparisons (one in loop header and another in the loop block) for each i .

I'm reporting the problem for ambiguity.

Prasun Biswas - 5 years, 5 months ago

Jose Solsona
Jan 5, 2016

Analytical approach, expressing the for loop as a summation:

$\sum_{i=0}^{n}1=1+\sum_{i=1}^{n}1=\boxed{n+1}$

Number of Comparisions (II)

Can you solve this as well?

2 solutions

0 pending reports