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

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

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.
• So I'm confused wouldn't the above formula be $E(T_i)$ what the question is looking for ? – mammy wood Apr 4 '19 at 7:32
• The formula involves the random variable $N_i$. – Yuval Filmus Apr 4 '19 at 7:37
• 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)$ – mammy wood Apr 4 '19 at 7:53