For the algorithm, give a function that describes the number of steps the algori
ID: 3811978 • 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
REVERSE3(A):
1 for every possible permutation P of A:
2 for index i = 1 to N:
3 if P[i] is not equal to A[N-i+1]:
continue to the next permutation
// All elements matched in proper places
4 return P
Given Next permutation takes one step,
step 1: Will iterate over all permutation in worst case. so, O(N!)
step 2: will iterate over size of array O(N) for all permutations
step 3: compares P[i] with A[N - i + 1] O(1)
step 4: O(1)
so, Total no of steps will be: N!* N.
For example:
A = {1, 2, 3, 4}
there will be 4! = 24 permutation.
all permutation will be checked and only last permutation will be reverse of A
P = {4, 3, 2, 1}
Total No of S