[RESOLVED] Number of steps and Complexity

[jamesking93]

Hi, I'm new to this forum
I'm studying computer science at uni and can't quite figure out this question.

What is the number of steps required when the input list size is 5?
What is the number of steps required with input list size n?
what is the complexity class of the algorithm?

Algorithm:

For list [L1,….,Ln].
1.     Put m=27, i=1.
2.     While i < n
            For j = i+1 to n
                If distance(Li,Lj) < m then m = distance(Li,Lj)
         i = i+1
3.     Return m.

In the algorithm, the function distance(α,β) is given by the absolute difference
between the position in the alphabet of α and β. For example, distance(b, f) = 4 and
distance(y, p) = 9.

If you could tell me how its worked out and what the answers are it would help me greatly.

Thanks in advance

[BioPhysEngr]

What do you have so far? How have you tried to count the number of statements executed?

[jamesking93]

not alot, I don't know where to start thats the problem :s

[BioPhysEngr]

Okay, well let's look at the loop:

The outer loop runs from 1 ... n-1 while the inner loop runs from i+1 ... n. Then, some distance calculation gets done. Thus, it looks like every pair of positions in the list is being compared (do you understand why?). How many unique comparisons can be performed between a set of n elements? (This is a named problem).

[umar2131]

I've had a bit of an issue with this question as well m gradually decreased for me until it reached 1 when 2 numbers are being compared then is it not similar to a bubble sort? However no swaps are made also however n values there are that's how many times this algorithm is executed so i would assume its of linear complexity?

[BioPhysEngr]

No, it is of quadratic complexity. To perform pairwise comparisons between all members of a set of size N requires N*(N-1)/2 comparisons. This is called the handshaking problem and has complexity O(N^2).

[umar2131]

Oh that helps a lot cheers just a quick question when I done the program there was 4 steps and n - 4 and the same for 5 so for the general case it would take n number of steps to execute? Thanks

[umar2131]

The thing is is that the question does not specify that unique comparisons need to be made if that is the case then its n^2-n/2 for general case n once again thanks for your help

[jamesking93]

cheers BioPhysEngr, I got it now.