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) Derive the expected length for the linked list just before the k'th operation is performed
so we need the weighted average of all possible values of some random variable. for each $X_i$ let it be the number of steps for given events. If theres a prepend we add a node whereas if theres an access we do nothing to the length. How do we come up with an equation for expectd length?
$E(X) = something \cdot (k-1)$ since just before $k$ but not sure how to derive the probability yet
Any help appreciated