Explore BrainMass

Describing Algorithms

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Suppose you are given a list of n integers in random order. Describe an algorithm that will determine whether the numbers would be an arithmetic progression if they were sorted. Note: An arithmetic progression is a set of numbers of the form {a + bj | j = 0, 1, 2, ... n - 1} where a and b are both integers. To get any marks your algorithm must run in O(n) time.

Please show me detailed processes, thank you.

https://brainmass.com/computer-science/sorting/describing-algorithms-164173

SOLUTION This solution is FREE courtesy of BrainMass!

1. Enter the n numbers one at a time in a "for loop" construct (O(n)).
2. The numbers are sorted in the numerical order using any O(n) algorithm, and the sorted sequence is stored in an array.
3. An arithmetic progression is a sequence of numbers wherein the difference between any two consecutive terms is a constant, called the common difference. Find the common difference between the first and the second terms in the sequence. This is an O(1) step.
4. Run a "for loop" with a Boolean control variable. For each run of the "for loop", find the difference between the (i+1)th and the ith term. If in any run of the loop, this difference comes out to be different from the common difference calculated in step 3, exit the for loop with the help of the Boolean variable. This iterative run is O(n).
5. Print the result in affirmative or negative, depending on the value of the Boolean variable. This step is O(1).

Therefore, the maximum time-complexity of this algorithm is O(n).

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!