0
$\begingroup$

I have an algorithm with running time depending on a parameter $ x \in (0, 1) $.

How is the asymptotic complexity of such algorithms typically analized?

In my particular case the running time approaches ∞ as x -> 1 but I don't know what I can say beyond that.

EDIT

More details about my particular algorithm:

The algorithm terminates when a given score S is reached (S is a parameter). On each iteration of the algorithm, S can either increase by 1 or be set to 0 (with probability x). I am looking to better understand the expected number of iterations as a function of x.

$\endgroup$
3
  • $\begingroup$ Can you describe your algorithm and its dependence on $x$ in more detail? $\endgroup$
    – zkutch
    Commented Jun 14, 2023 at 11:00
  • $\begingroup$ @zkutch I added more details to the question. $\endgroup$
    – martinkunev
    Commented Jun 14, 2023 at 11:23
  • $\begingroup$ Running time is often a function of its inputs. You can approximate the mean (a function of $S$ and $x$) and worst case (infinite) complexities. $\endgroup$
    – Eric
    Commented Jun 14, 2023 at 12:34

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .