[Algoritmi] problema

[checcosette7]

scusate ma non riesco a capire come progettare questo algoritmo tratto da un appello.

Sia v[1:n] un vettore di n numeri positivi (distinti) ordinato in modo crescente. Dato a>1, progettare un algoritmo che restituisca una coppia di indici i,j, che massimizza j-i e tale che V[j]<= a V.
per esempio se a=3, V=[1,3,5,6,10,12,20,38] la soluzione ottima è i=3 e j=6. la complessità temporale deve essere o($n^2$)

[onlyReferee]

Ciao checcosette7
Allora, sicuramente ti servono due $\text{for}$ annidati per scorrere l'array ed eseguire i vari confronti. Per il resto basta che scrivi l'$\text{if}$ ed esegui il confronto, sostituendo o meno in base allo stesso le tue variabili per gli indici finali che ci interessano (più quello contenente il valore della differenza tra $i$ e $j$).

[apatriarca]

L'idea principale è quella di avere un ciclo esterno che per ogni indice \(i\) dell'array esegue il ciclo interno per trovare il massimo \(j\) per cui \(V[j] \leq a\,V\). Siccome i valori contenuti in V sono ordinate in modo crescente, puoi fermarti al primo valore per cui quella condizione non sia verificata.

P.S. È anche possibile fare un algoritmo con tempo O(n)..

[checcosette7]

grazie per la risposta.
come sarebbe possibile in O(n)? perchè il testo chiede o($n^2$) e non O($n^2$), ma una migliore risoluzione è sempre preferibile in generale