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:

1e707a0ccd28cafaf43fb418dd727d8cbd1fd7d6.png


ma io non riesco assolutamente ad arrivarci. Qualche anima pia riuscirebbe a spiegarmi i vari passi?


Grazie anticipatamente!