[Algoritmi] Complessità computazionale del metodo "lastIndexOf"

[ReaSanka]

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
https://ibb.co/jmaeuv
ma io non riesco assolutamente ad arrivarci. Qualche anima pia riuscirebbe a spiegarmi i vari passi?

P.s. Se dovesse essere un problema la mia immagine mi scuso anticipatamente. (non riuscivo a caricarla e così ho messo il link)

Grazie anticipatamente!

[wingman87]

Perché il caso peggiore è 2n+1? n cos'è? Il caso peggiore è n dove n è la lunghezza della stringa. La soluzione del caso medio riportata nell'immagine presuppone che il carattere cercato compaia con una probabilità di 1/26 ma non capisco la moltiplicazione per 2i, dovrebbe essere moltiplicato per i.

Inviato dal mio F5121 utilizzando Tapatalk