For the algorithm, give a function that describes the number of steps the algori
ID: 3811977 • Letter: F
Question
For the algorithm, give a function that describes the number of steps the algorithm will take on an input of N elements in the worst case. You can be off by up to a constant multiplicative factor, or off by an additive constant. For example, if the algorithm were linear search on an ordered array, N would be a correct answer, while the answer of 2N+3 would still be acceptable (if a bit out of nowhere). Assume the first element of the array is element 1 (as opposed to 0).
3. REVERSE3(A): // Reverse the order of elements in an array
// P is an array; assume generating next permutation takes 1 step.
for every possible permutation P of A:
for index i = 1 to N:
if P[i] is not equal to A[N-i+1]:
continue to the next permutation
// All elements matched in proper places
return P
Explanation / Answer
//to find the number of steps taken is
//add a additive constant to reverse3
//this function will return the number of steps...taken/
3. count_REVERSE3(A): // Reverse the order of elements in an array
// P is an array; assume generating next permutation takes 1 step.
c = 0;//constant..to count the steps
for every possible permutation P of A:
for index i = 1 to N:
if P[i] is not equal to A[N-i+1]:
{continue to the next permutation
c++;//counting steps...
}
// All elements matched in proper places
return c//returning count...
//the worst case complexity of this algorithm is (n!*n) where n is size of input array...