www-ai.cs.tu-dortmund.de/LEHRE/FACHPROJEKT/SS12/paper/counting/Arasu2004.pdf
of level-` blocks by N`. We set N0 = εW
4 3 and for ` ≥ 1, N` = 2N`−1. It fol-
lows that N` = 2`N0 = εW 4
2`. Note that NL = W . Within a level, blocks are numbered 0, 1, 2, . . .; smaller numbered blocks [...] corresponding to all the active blocks is O( L
`=0 2L−`/ε`). Substituting ε` = ε
2(2L+2) 2(L−`), the required space is O( L
`=0 2(2L + 2)/ε),
which is O( L `=0
L ε ) = O(L2
ε ) = O( 1
ε log2 1
ε ).
By definition [...] corresponding to all the active blocks is O( L
`=0 2L−`/ε`). Substituting ε` = ε 2(2L+2)
2(L−`), the re-
quired space is O( L `=0 2(2L+2)/ε), which is O( L
`=0 L ε ) =
O(L2
ε ) = O( 1
ε log2 1
ε ).
There …
