1 log ) • Update Time per element: log 1 Optimization: Sampling the input • Space: (1 log1.5 1 ) • Update Time per element: log 1 – Decreasing to (1) as → ∞
for an insertion or a deletion New element Data set Ins 3 3 Ins 14 3, 14 Ins 15 3, 14, 15 Del 3 14, 15 Ins 26 14, 15, 26 Del 14 15, 26 Ins 53 15, 26, 53
ESCAPE 2007 Random Subset Sum 1 2 log2 Gilbert et al. VLDB 2002 DCM 1 log2 Cormode & Muthukrishnan J. of Algorithms 2005 DCS 1 log1.5 New * Small log factors are ignored.