Expected runtime of recursive algorithm with optional part

Question

I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$ T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends on $T(n-i)$ for some values of $i$, and $c$ is some constant. I want to add a procedure to this algorithm that samples the input data and performs some computation with it. There are two outcomes to this procedure: if it is positive, then let the algorithm proceed as normal; if it is negative, then sample and perform the computation again. Suppose that the added procedure runs in at most $d\cdot g(n)$ time for some constant $d$.

How can I write the recursion for the expected running time for this new algorithm?

• user16034: "that depends on $T(n-i)$" is too vague. (And more generally, the description is not really understandable.)
• user16034: What is the purpose of splitting $d\cdot g$ ?

Answer 1

If the probability for resampling is $p(n)$, then the running time satisfies $$ T(n) \leq Cn + R + p(n) \cdot d g(n). $$

• joeren1020: Shouldn't the term 1ドル-p(n)$ also appear, like in $T(n) \leq d\cdot g(n) + p(n)\cdot d g(n) + (1-p(n))(cn + R)$?
• Yuval Filmus: When you don't resample, you don't do anything, so you don't need to add any terms for this. It is true that you have new logic in your algorithm that might increase the "$Cn+R$" part, but it can probably be swallowed inside $C$ or inside $R$.
• joeren1020: I'm still trying to understand why the term $(1 - p(n))$ doesn't appear and why you say that the algorithm doesn't do anything when it doesn't resample. Isn't is true that when the algorithm does not resample it proceeds as normal meaning that it calls the recursion again? Could you please elaborate on this?
• Yuval Filmus: A bound $T(n) \le Cn+R$ doesn’t represent a recursion.
• user16034: @YuvalFilmus: it does as $R$ depends on "some" $T(n-i)$.