Lower bound on algorithm solving certain recurrence I have to find the lower bound of the following recursion:
$A_1 = C_1 = p_1$, $B_1 = D_1 = 1-p_1$, $F_k = A_k + B_k$. Evaluate $F_n$.
\begin{align}
A_{k+1} &amp;= (A_k + 2C_k) p_{k+1} + (1-p_k) p_{k+1}, \\
B_{k+1} &amp;= (B_k + 2D_k) (1-p_{k+1}) + p_k (1-p_{k+1}), \\
C_{k+1} &amp;= C_k p_{k+1} + (1-p_k) p_{k+1}, \\
D_{k+1} &amp;= D_k (1-p_{k+1}) + p_k (1-p_{k+1}).
\end{align}
In this case all numbers of the form $p_i$ are given inputs (there are $n$ of them).
I have to find the lower bound of this algorithm.
Since it's runtime is just $O(n)$ (right?), I know for sure that the maximum possible value of the lower bound is $\Omega(n)$. How would I go about proving/disproving that $\Omega(n)$ truly is the minimum bound  and that $\Omega(n-1)$ is not/is attainable?
The only main method I know for proving stuff like this is an Adversary Argument but after a couple hours of thinking, I still haven't been able to come up with an argument to prove what I want.
Any helps/tips/suggestions would be greatly appreciated.
There's quite a lot of confusion here:

$\Omega(n)$ and $\Omega(n-1)$ are absolutely the same.
You don't an adversary argument to show that this algorithm runs in $\Theta(n)$. It follows immediately from the description of the argument.
There is a difference between analyzing the running time of a particular algorithm and showing that every algorithm that correctly solves a problem must run in at least so many steps.

In order to show that any algorithm computing $F_n$ correctly must run in time $\Omega(n)$, we will show that any such algorithm must read all inputs $p_1,\ldots,p_n$. The starting point is the following observation:

The correct output is different for the instances $p_1=\cdots=p_n=0$ and $p_1=\cdots=p_{i-1}=0,p_i=1,p_{i+1}=\cdots=p_n=0$.

Given that, we can use a simple adversary argument to show that any algorithm correctly computing the function must read all $p_j$. Indeed, run the given algorithm, answering $0$ whenever it queries the value of some $p_j$. If it announces the answer without querying, say, $p_i$, then it cannot tell apart the two instances above, and in particular, its answer will be wrong on at least one of them.