Limite inferiore sull'algoritmo che risolve determinate ricorrenze

Question

Devo trovare il limite inferiore della seguente ricorsione:

$A_1 = C_1 = p_1$, $B_1 = D_1 = 1-p_1$, $F_k = A_k + B_k$. Valutare$F_n$. \begin{align} A_{k+1} &= (A_k + 2C_k) p_{k+1} + (1-p_k) p_{k+1}, \\ B_{k+1} &= (B_k + 2D_k) (1-p_{k+1}) + p_k (1-p_{k+1}), \\ C_{k+1} &= C_k p_{k+1} + (1-p_k) p_{k+1}, \\ D_{k+1} &= D_k (1-p_{k+1}) + p_k (1-p_{k+1}). \end{align}

In questo caso tutti i numeri del modulo $p_i$ sono dati input (ci sono $n$ di loro).

Devo trovare il limite inferiore di questo algoritmo.

Dal momento che è runtime è solo $O(n)$ (giusto?), so per certo che il valore massimo possibile del limite inferiore è $\Omega(n)$. Come potrei provarlo / confutarlo$\Omega(n)$ è veramente il limite minimo e quello $\Omega(n-1)$ non è / è raggiungibile?

L'unico metodo principale che conosco per provare cose del genere è un argomento avversario, ma dopo un paio d'ore di riflessione, non sono ancora riuscito a trovare un argomento per dimostrare quello che voglio.

Eventuali aiuti / suggerimenti / suggerimenti sarebbero molto apprezzati.

Answer 1

C'è molta confusione qui:

1. $\Omega(n)$ e $\Omega(n-1)$ sono assolutamente gli stessi.
2. Non sei un argomento avversario per dimostrare che questo algoritmo viene eseguito $\Theta(n)$. Segue immediatamente dalla descrizione dell'argomento.
3. C'è una differenza tra l'analisi del tempo di esecuzione di un particolare algoritmo e il mostrare che ogni algoritmo che risolve correttamente un problema deve essere eseguito in almeno tanti passaggi.

Per dimostrare che qualsiasi algoritmo di calcolo$F_n$ correttamente deve funzionare nel tempo $\Omega(n)$, mostreremo che qualsiasi algoritmo di questo tipo deve leggere tutti gli input $p_1,\ldots,p_n$. Il punto di partenza è la seguente osservazione:

L'output corretto è diverso per le istanze $p_1=\cdots=p_n=0$ e $p_1=\cdots=p_{i-1}=0,p_i=1,p_{i+1}=\cdots=p_n=0$.

Detto questo, possiamo usare un semplice argomento avversario per mostrare che qualsiasi algoritmo che calcola correttamente la funzione deve leggere tutto $p_j$. Effettivamente, esegui l'algoritmo dato, rispondendo$0$ ogni volta che interroga il valore di alcuni $p_j$. Se annuncia la risposta senza fare domande, ad esempio,$p_i$, quindi non può distinguere i due casi sopra, e in particolare, la sua risposta sarà sbagliata su almeno uno di essi.