[Algoritmi] Complessità computazionale del metodo "lastIndexOf"

[Calliope]

Salve a tutti, sono nuova e spero di aver azzeccato la categoria. Sto studiando algoritmi e strutture dati e sono un po' in difficoltà con gli esercizi sulla complessità. Quando credo di averli capiti, poi spunta qualcosa che mi fa ricredere. Comunque, l'esercizio che vi sottopongo è questo:

Analizzare la complessità di questo algoritmi che prende in input un array e restituisce l'ultima occorrenza di una lettera (in questo caso la g):

public static int lastIndexOf(char g, char[] S) {
int j;
for (j = S.length-1; j>=0; j--) {
if (S[j] == g) {
return j;
}
return -1;
}



per quanto riguarda il caso ottimo, f(n) =1, per quanto riguarda invece il caso pessimo f(n) = 2n + 1 .
Ho problemi invece con il caso medio.. il risultato dovrebbe essere questo:

https://ibb.co/jmaeuv
ma io non riesco assolutamente ad arrivarci. Qualche anima pia riuscirebbe a spiegarmi i vari passi?

P.s. ho visto che nelle altre discussioni riuscite a scrivere le formule. Se dovesse essere un problema la mia immagine e se mi spiegate come fare, modifico il mio topic.

Grazie anticipatamente!

[xneo]

Il caso ottimo è se la 'g' si trova alla fine dell'array, in questo caso la complessità temporale è O(1).
Il caso peggiore è se la 'g' si trova alla fine o non è presente, in questo caso la complessità è O(n).
Il caso medio è ancora O(n) che deriva dalla somma da i (indice della 'g') da 1 a n e dividere tutto per n (devi fare la media di tutti i casi). Ho omesso il caso in cui la 'g' non è presente, ma questo cambierebbe solo qualche costante.