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.


1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – theGrind24
    Commented Nov 20, 2020 at 15:03
  • $\begingroup$ 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. $\endgroup$ Commented Nov 20, 2020 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.