Number of Comparisons (I)

Computer Science Level 2

How may comparisons are done in the following algorithm ?

    // Start here

    a := 0
    for i := 1 to n
        for j := i to 1
            if j mod i := 0
                a := a+1
            j := j-1
        i := i+1
    return a

    // Stop here

This problem is a part of the set: Efficient Algorithms .

n^{2}

n^{2} \times (n-1)

\frac{n \times (n+1)}{2}

\frac{n+1}{2}

2 solutions

Zeeshan Ali
Dec 21, 2015

The outer-most loop will run n times as under;

$1^{st}$ time: and the inner-loop will run 1 time

$2^{nd}$ time: and the inner-loop will run 2 times

$3^{rd}$ time: and the inner-loop will run 3 times

$4^{th}$ time: and the inner-loop will run 4 times

$(n-1)^{th}$ time: and the inner-loop will run (n-1) times

$n^{th}$ time: and the inner-loop will run n times

Hence the total number of comparisons done are 1+2+3+4+...+(n-1)+n= $\boxed{\frac{n(n+1)}{2}}$ .

I hope the above solution will help you all to have a better understanding.

I guess you have mistyped and placed - instead of + in the last part of your solution.

Harshvardhan Mehta - 5 years, 5 months ago

Oops! Right.. Thank you sir!

Zeeshan Ali - 5 years, 5 months ago

Jose Solsona
Jan 2, 2016

Analytical approach, expressing every for loop as a summation:

$\sum_{i=1}^{n}\sum_{j=1}^{i}1=\sum_{i=1}^{n}i=\boxed{\frac{n(n+1)}{2}}$

Number of Comparisons (I)

This problem is a part of the set: Efficient Algorithms .

2 solutions

0 pending reports