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

There's quite a lot of confusion here:

1. $$\Omega(n)$$ and $$\Omega(n-1)$$ are absolutely the same.
2. You don't an adversary argument to show that this algorithm runs in $$\Theta(n)$$. It follows immediately from the description of the argument.
3. 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.

• I have a couple of questions: 1. why does proving that the algorithm needs all $n$ inputs mean that it runs in $\Omega(n)$ time? 2. The problem asks "Give the best lower bounds you can on a runtime of such an algorithm." Would that mean for all of the possible algorithms, I need to come up with the shortest one out of all of them? 3. If it asks for the best possible lower bounds, would arguing a lower bound of say $\Omega{5n}$ be considered as "better" than $\Omega{n}$ since technically, it is a more tight bound? Nov 20 '20 at 15:03
• I'm not sure you have a very good grasp of the meaning of "$\Omega(n)$". We have several reference questions covering asymptotic notations. You can start here. Nov 20 '20 at 15:34