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


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 Apr 4 '19 at 7:13
  • $\begingroup$ In your case, expected number of steps. $\endgroup$ – Yuval Filmus Apr 4 '19 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 Apr 4 '19 at 7:32
  • $\begingroup$ The formula involves the random variable $N_i$. $\endgroup$ – Yuval Filmus Apr 4 '19 at 7:37
  • $\begingroup$ Not sure how to do it that way but I tried something similar $E(X) = p \cdot \frac{\sum_{i=1}^{1+p(k-1)}}{1+p(k-1)} + (1-p) \cdot 1$ $ = p \frac{1+2 \cdots + (1+p(k-1))}{(1+p(k-1))} + 1 - p$ $ = p \frac{p(k-1)}{2} + 1 - p$. Since $N_i = 1 + p(k-1)$ $\endgroup$ – mammy wood Apr 4 '19 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.