# Expected runtime of recursive algorithm with optional part

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?

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

If the probability for resampling is $$p(n)$$, then the running time satisfies $$T(n) \leq Cn + R + p(n) \cdot d g(n).$$
• 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)$? Commented Oct 5, 2022 at 22:24
• 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$. Commented Oct 6, 2022 at 6:07
• 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? Commented Oct 21, 2022 at 20:07
• A bound $T(n) \le Cn+R$ doesn’t represent a recursion. Commented Oct 23, 2022 at 21:24
• @YuvalFilmus: it does as $R$ depends on "some" $T(n-i)$.