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} &= (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 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.