www-ai.cs.tu-dortmund.de/de/LEHRE/FACHPROJEKT/SS12/paper/counting/lee2006.pdf
e(Wp) + 2λj+1 = ne(Wp) + ε2j+1/8 and hence
dB < 2j + 16
ε ( ε2j+1
8 ) + k22
j+1
16 ε
= (5 + 2k2)ε2
j
16
Therefore, the number d of batches of decrements in I is
d = dA + dB < (5 + 2k1)ε2
j
16 +
(5 + 2k2)ε2 [...] level h, we have curblkh = 3, offseth = 2, Qh,e = 〈1, 2, 3〉 and h,e = 2. Then in level h + 1, we set curblkh+1 = 3/2 = 2, offseth+1 = 2, Qh+1,e = 〈1〉 and h+1,e = λh + 2 = 5.
In the rest of this section, we [...] 2k2)ε2 j
16
= (10 + 2k)ε2j
16 =
(5 + k)ε2j+1
16
Case 2. The interval I of size k2j+1 is in interval B only. Just before executing Update on the first bit in interval I , there are at most 2j+1 items in the sliding …