3 added 3 characters in body; edited tags; edited title
source | link

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$.

    Tweeted twitter.com/#!/StackCompSci/status/540320212818853888
2 added 310 characters in body
source | link

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
source | link

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?