Amortized Time Cost using Accounting Method

Question

I written an algorithm to calculate the next lexicographic permutation of an array of integers (ex. 123, 132, 213, 231, 312,323). I dont think the code is necessary but I included it below.

I think I have appropriately determined worst case time cost of O(n) where n is the number of elements in the array. I understand however if you utilize "Amortized Cost" you would find that the time cost could be accurately shown as O(1) on average case.

Question:

I would like to learn the "ACCOUNTING METHOD" to show this as O(1) but am having difficulty understanding how to apply a cost to each operation. Accounting method: Link: Accounting_Method_Explained

Thoughts:

Ive thought to apply a cost of changing a value at a position, or applying the cost to a swap. But it really doesnt make much sense.

public static int[] getNext(int[] array) {
int temp;
int j = array.length - 1;
int k = array.length - 1;

// Find largest index j with a[j] < a[j+1]
// Finds the next adjacent pair of values not in descending order
do {
    j--;
    if(j < 0)
    {
        //Edge case, where you have the largest value, return reverse order
        for(int x = 0, y = array.length-1; x<y; x++,y--)
        {
            temp = array[x];
            array[x] = array[y];
            array[y] = temp;
        }
        return array;
    }
}while (array[j] > array[j+1]);

// Find index k such that a[k] is smallest integer
// greater than a[j] to the right of a[j]
for (;array[j] > array[k]; k--,count++);

//Swap the two elements found from j and k
temp = array[k];
array[k] = array[j];
array[j] = temp;

//Sort the elements to right of j+1 in ascending order
//This will make sure you get the next smallest order
//after swaping j and k
int r = array.length - 1;
int s = j + 1;

while (r > s) {
    temp = array[s];
    array[s++] = array[r];
    array[r--] = temp;
}
  return array;

} // end getNext

Answer 1

From the aggregate analysis, we see T(n) < n! · e < n! · 3, so we pay $3 for each operation, and its enough for the total n! operations. Therefore its an upper bound of actual cost. So the total amortized

Answer 2

1. Measure running time in swaps, since the other work per iteration is worst-case O(#swaps).
2. The swap of array[j] and array[k] has virtual cost 2. The other swaps have virtual cost 0. Since at most one swap per iteration is costly, the running time per iteration is amortized constant (assuming that we don't go into debt).
3. To show that we don't go into debt, it suffices to show that, if the swap of array[j] and array[k] leaves a credit at position j, then every other swap involves a position with a credit available, which is consumed. Case analysis and induction reveal that, between iterations, if an item is larger than the one immediately following it, then it was put in its current position by a swap that left an as-yet unconsumed credit.
4. This problem is not a great candidate for the accounting method, given the comparatively simple potential function that can be used: number of indexes j such that array[j] > array[j + 1].