Next, we look at the runtimes for Algorithm REF  and Algorithm REF  to handle one deletion or insertion request. For this, we look at the runtime of verification, i.e., deciding if recompute needs to be triggered or not. We show how in the standard algorithmic model of computation (say, word RAM model), using suitable data structures, this can be done efficiently. Furthermore, as standard in convex optimization, we can use Nemirovski-Yudin's model of computation [1]} which counts the number of accesses to the first-order (gradient) information of the function, and a projection oracle.
Let \(\mathfrak {G}\)  denote the compute cost for one gradient access or projection in the standard model of computation –
we assume that both oracles require the same compute. In the rest of the discussion, we provide runtime as a function of the problem parameters ignoring all constants. Furthermore, since we assumed that the number of samples at any point in the stream is between \(\frac{n}{2}\)  and \(2n\) , we will just work with \(n\)  samples, and everything would still be the same, up to constants.
