# Find the Lower Bound of the Algorithm

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.