0
$\begingroup$

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?

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

1 Answer 1

0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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)$? $\endgroup$
    – joeren1020
    Oct 5, 2022 at 22:24
  • $\begingroup$ 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$. $\endgroup$ Oct 6, 2022 at 6:07
  • $\begingroup$ 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? $\endgroup$
    – joeren1020
    Oct 21, 2022 at 20:07
  • $\begingroup$ A bound $T(n) \le Cn+R$ doesn’t represent a recursion. $\endgroup$ Oct 23, 2022 at 21:24
  • $\begingroup$ @YuvalFilmus: it does as $R$ depends on "some" $T(n-i)$. $\endgroup$
    – user16034
    Jul 4, 2023 at 6:54

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.