Consider a datatype whose objects will be sequences of elements that has the following two methods

prepend($x, T$) which will insert an element to x to the beginning of the sequence T

search($T, i$) which returns the ith element in the given sequence

T is a linked list. prepend takes $1$ step. Search takes $i$ steps

Suppose T has exactly one element and a sequence of n operations are performed. You are given that prepend has probability $p$ and search has probability $1-p$ for each operation. The value of $i$ is chosen uniformly from $[1, \dots, T]$

Q) Deriving the expected number of steps that is taken to perform the k'th operation

This would be the average of all possible events so number of search and prepends to the expected length. Expected length is given to be p (k-1). Derived from below

expected length of linked list

search takes i steps (probability 1-p). Prepend takes 1 step (probability is p ).

$E(X) = search(1) + search(2) + \cdots + search((p(k-1)))$

Not sure how to get an exact value for it


1 Answer 1


Let $N_i$ be the random variable denoting the length of $T$ prior to the $i$th operation. You should be able to calculate $\mathbb{E}[N_i]$.

The expected running time $T_i$ of the $i$th operation is $$ p \cdot 1 + (1-p) \cdot \frac{1+\cdots+N_i}{N_i} = p + (1-p) \frac{N_i+1}{2}. $$ Given $\mathbb{E}[N_i]$, you should be able to calculate $\mathbb{E}[T_i]$ using this formula.

I leave you to figure out all remaining details.

  • $\begingroup$ "The expected running time Ti of the ith operation is" what does this mean? Expected running time, is that expected number of steps ? $\endgroup$
    – mammy wood
    Commented Apr 4, 2019 at 7:13
  • $\begingroup$ In your case, expected number of steps. $\endgroup$ Commented Apr 4, 2019 at 7:20
  • $\begingroup$ So I'm confused wouldn't the above formula be $E(T_i)$ what the question is looking for ? $\endgroup$
    – mammy wood
    Commented Apr 4, 2019 at 7:32
  • $\begingroup$ The formula involves the random variable $N_i$. $\endgroup$ Commented Apr 4, 2019 at 7:37
  • 1
    $\begingroup$ Note that $N_i$ is a random variable. It is not equal to $1+p(k-1)$, though its expectation is. $\endgroup$ Commented Apr 4, 2019 at 8:19

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.