An exercise I made for myself about probabilistic analysis (PERMUTE-SORT)

Question

I'm trying to learn about probabilistic analysis of algorithms, so I made some exercises for myself to try to solve. One of these exercises I don't understand how to solve:
Given the following algorithm:

PERMUTE_SORT(A)
if IS_SORTED(A) then 
    return A 
else 
    return PERMUTE(A)

Assuming that IS_SORTED runs in $O(n)$, where $n$ is the length of the array, PERMUTE(A) runs in constant time, and that we only go through each permutation once:

(A). What's the best case runtime? (B). What's the worst case runtime? (C). What's the average case runtime?

Here's my solution: (A). O(1), if A is already sorted. (B). O(n!), if we go through each permutation

But I don't understand how to approach (C). I'm looking for a hint on how to approach this and not the full solution. Thanks!

Edit: I made some progress in (C). Is this correct?

Let $C_n$ be the number of permutations we go through. Let $P_i$ be the ith permuatation. Let $X_i = I\{We\ went\ through\ permutation\ i\}$. Then $C_n = \sum_{i = 1}^{n!} X_i$, and correspondingly $E[C_n] = E[\sum^{n!}_{i = 1} X_i]$. From the linearity of the expected value, we have $E[C_n] = \sum_{i = 1}^{n!} E[X_i]$. But $E[X_i]$ is the probability of going through permutation $i$, which is $\frac{1}{n!}$. If so, we have $E[C_n] = \sum^{n!}_{i = 1} \frac{1}{n!}$, which is $n!$. If so, the average case runtime is $\Theta(n)!$.

Answer 1

If PERMUTE moves through all permutations in some predetermined order, then there is a permutation that takes zero applications until it is sorted, a permutation that takes 1 application until it is sorted (the preimage of the previous one) etc. So on average we need $$ \frac{1}{n!} \sum_{i=1}^{n!} i = \frac{1}{n!} \frac{n!(n!+1)}{2} = \Theta ( n! ) $$ applications of PERMUTE to reach a sorted permutation. Now as IS_SORTED takes $O(n)$ and PERMUTE takes constant time, the average case runtime is $O(n \cdot n!)$.

Also, the best case is $O(n)$ because even for the sorted permutation we still need to check once that it is sorted. Similarly, the worst case runtime is $O(n \cdot n!)$ as well.

Edit: Also I feel I should mention, there is some sloppiness in your calculations with the expected value. In particular, $\sum_{i=1}^{n!} \frac{1}{n!}$ does not equal $n!$, but instead equals $1$. So this is incorrect. Moreover, you claim that $E X_i = \frac{1}{n!}$, where I use the notation from your edit. This however is also false, take for instance the sorted permutation, then the probability of encountering this permutation at some point during the iteration is in fact equal to $1$, because only then do we stop iterating. I hope this clears some things up and that the solution I propose above is clear.