CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: [RESOLVED] Number of steps and Complexity

1. Junior Member
Join Date
Mar 2012
Posts
3

## [RESOLVED] Number of steps and Complexity

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:
Code:
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.

2. ## Re: Number of steps and Complexity

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

3. Junior Member
Join Date
Mar 2012
Posts
3

## Re: Number of steps and Complexity

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

4. ## Re: Number of steps and Complexity

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

5. Junior Member
Join Date
Mar 2012
Posts
3

## Re: Number of steps and Complexity

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?

6. ## Re: Number of steps and Complexity

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

7. Junior Member
Join Date
Mar 2012
Posts
3

## Re: Number of steps and Complexity

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

8. Junior Member
Join Date
Mar 2012
Posts
3

## Re: Number of steps and Complexity

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

9. Junior Member
Join Date
Mar 2012
Posts
3

## Re: [RESOLVED] Number of steps and Complexity

cheers BioPhysEngr, I got it now.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts