# Describing Algorithms

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.

Â© BrainMass Inc. brainmass.com December 24, 2021, 7:07 pm ad1c9bdddfhttps://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).

Â© BrainMass Inc. brainmass.com December 24, 2021, 7:07 pm ad1c9bdddf>https://brainmass.com/computer-science/sorting/describing-algorithms-164173