3 added 3 characters in body; edited tags; edited title

# Time Complexity Asymptotic expected runtime of Randomized Algorithm

I am analyzing the time complexityasymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties:

• Given input size $$n$$, with probability $$3/4$$ it moves on to solve an instance of size $$n-1$$
• With probability $$1/8$$ it moves on to solve an instance of size $$n-2$$
• With probability $$1/16$$ it moves on to solve an instance of size $$n-3$$
• With probability $$1/2^i$$ it moves on to solve an instance of size $$n-i$$
• Each instance pays a cost of $$O(n)$$, where $$n$$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$$

$$T(0) = O(1)$$

I have calculated that the expected number of "jumps" at each stage is $$\leq 1$$. I did this by showing $$\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $$n$$ gets smaller, although this hints the runtime is $$O(n^2)$$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

EDIT: Slight gap in my formulation. The "$$3/4$$" probability for moving onto an instance of size $$n-1$$ should actually be larger than $$3/4$$ since the probabilities $$1/2, 1/4, 1/8, ...$$ only go on till $$1/2^{n+1}$$. If no jumps were made, the algorithm deterministically moves on to an instance of size $$n-1$$.

# Time Complexity of Randomized Algorithm

I am analyzing the time complexity of a randomized algorithm in expectation. The algorithm has the following properties:

• Given input size $$n$$, with probability $$3/4$$ it moves on to solve an instance of size $$n-1$$
• With probability $$1/8$$ it moves on to solve an instance of size $$n-2$$
• With probability $$1/16$$ it moves on to solve an instance of size $$n-3$$
• With probability $$1/2^i$$ it moves on to solve an instance of size $$n-i$$
• Each instance pays a cost of $$O(n)$$, where $$n$$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$$

$$T(0) = O(1)$$

I have calculated that the expected number of "jumps" at each stage is $$\leq 1$$. I did this by showing $$\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $$n$$ gets smaller, although this hints the runtime is $$O(n^2)$$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

EDIT: Slight gap in my formulation. The "$$3/4$$" probability for moving onto an instance of size $$n-1$$ should actually be larger than $$3/4$$ since the probabilities $$1/2, 1/4, 1/8, ...$$ only go on till $$1/2^{n+1}$$. If no jumps were made, the algorithm deterministically moves on to an instance of size $$n-1$$.

# Asymptotic expected runtime of Randomized Algorithm

I am analyzing the asymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties:

• Given input size $$n$$, with probability $$3/4$$ it moves on to solve an instance of size $$n-1$$
• With probability $$1/8$$ it moves on to solve an instance of size $$n-2$$
• With probability $$1/16$$ it moves on to solve an instance of size $$n-3$$
• With probability $$1/2^i$$ it moves on to solve an instance of size $$n-i$$
• Each instance pays a cost of $$O(n)$$, where $$n$$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$$

$$T(0) = O(1)$$

I have calculated that the expected number of "jumps" at each stage is $$\leq 1$$. I did this by showing $$\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $$n$$ gets smaller, although this hints the runtime is $$O(n^2)$$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

EDIT: Slight gap in my formulation. The "$$3/4$$" probability for moving onto an instance of size $$n-1$$ should actually be larger than $$3/4$$ since the probabilities $$1/2, 1/4, 1/8, ...$$ only go on till $$1/2^{n+1}$$. If no jumps were made, the algorithm deterministically moves on to an instance of size $$n-1$$.

2 added 310 characters in body

I am analyzing the time complexity of a randomized algorithm in expectation. The algorithm has the following properties:

• Given input size $$n$$, with probability $$3/4$$ it moves on to solve an instance of size $$n-1$$
• With probability $$1/8$$ it moves on to solve an instance of size $$n-2$$
• With probability $$1/16$$ it moves on to solve an instance of size $$n-3$$
• With probability $$1/2^i$$ it moves on to solve an instance of size $$n-i$$
• Each instance pays a cost of $$O(n)$$, where $$n$$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$$

$$T(0) = O(1)$$

I have calculated that the expected number of "jumps" at each stage is $$\leq 1$$. I did this by showing $$\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $$n$$ gets smaller, although this hints the runtime is $$O(n^2)$$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

EDIT: Slight gap in my formulation. The "$$3/4$$" probability for moving onto an instance of size $$n-1$$ should actually be larger than $$3/4$$ since the probabilities $$1/2, 1/4, 1/8, ...$$ only go on till $$1/2^{n+1}$$. If no jumps were made, the algorithm deterministically moves on to an instance of size $$n-1$$.

I am analyzing the time complexity of a randomized algorithm in expectation. The algorithm has the following properties:

• Given input size $$n$$, with probability $$3/4$$ it moves on to solve an instance of size $$n-1$$
• With probability $$1/8$$ it moves on to solve an instance of size $$n-2$$
• With probability $$1/16$$ it moves on to solve an instance of size $$n-3$$
• With probability $$1/2^i$$ it moves on to solve an instance of size $$n-i$$
• Each instance pays a cost of $$O(n)$$, where $$n$$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$$

$$T(0) = O(1)$$

I have calculated that the expected number of "jumps" at each stage is $$\leq 1$$. I did this by showing $$\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $$n$$ gets smaller, although this hints the runtime is $$O(n^2)$$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

I am analyzing the time complexity of a randomized algorithm in expectation. The algorithm has the following properties:

• Given input size $$n$$, with probability $$3/4$$ it moves on to solve an instance of size $$n-1$$
• With probability $$1/8$$ it moves on to solve an instance of size $$n-2$$
• With probability $$1/16$$ it moves on to solve an instance of size $$n-3$$
• With probability $$1/2^i$$ it moves on to solve an instance of size $$n-i$$
• Each instance pays a cost of $$O(n)$$, where $$n$$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$$

$$T(0) = O(1)$$

I have calculated that the expected number of "jumps" at each stage is $$\leq 1$$. I did this by showing $$\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $$n$$ gets smaller, although this hints the runtime is $$O(n^2)$$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

EDIT: Slight gap in my formulation. The "$$3/4$$" probability for moving onto an instance of size $$n-1$$ should actually be larger than $$3/4$$ since the probabilities $$1/2, 1/4, 1/8, ...$$ only go on till $$1/2^{n+1}$$. If no jumps were made, the algorithm deterministically moves on to an instance of size $$n-1$$.

1

# Time Complexity of Randomized Algorithm

I am analyzing the time complexity of a randomized algorithm in expectation. The algorithm has the following properties:

• Given input size $$n$$, with probability $$3/4$$ it moves on to solve an instance of size $$n-1$$
• With probability $$1/8$$ it moves on to solve an instance of size $$n-2$$
• With probability $$1/16$$ it moves on to solve an instance of size $$n-3$$
• With probability $$1/2^i$$ it moves on to solve an instance of size $$n-i$$
• Each instance pays a cost of $$O(n)$$, where $$n$$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$$

$$T(0) = O(1)$$

I have calculated that the expected number of "jumps" at each stage is $$\leq 1$$. I did this by showing $$\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $$n$$ gets smaller, although this hints the runtime is $$O(n^2)$$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?