IBDRE _{ZCZ16}

\(\mathcal {O}(\log {Q})\)

\(\mathcal {O}(n^{6.5+7.5\eta +4c})\)

\(\mathcal {O}(n^{2.5+3.5\eta +2c})\)

\(\mathcal {O}(n^{3+3\eta +2c})^{\dag }\)

\(\mathcal {O}\left (n^{0.5}\right)\)

\(\mathcal {O}\left (\frac {\epsilon }{\ell ^{2}Q^{4}}\right)\)

IBDRE _{Yam16}

\(\omega (\sqrt {n})\)

\(\mathcal {O}(n^{5.5+3.5\eta +2c})\)

\(\mathcal {O}(n^{2+1.5\eta +c})\)

\(\mathcal {O}(n^{2.5+\eta +c})\ddag \)

\(\mathcal {O}\left (n^{0.5}\right)\)

\(\mathcal {O}\left (\frac {\epsilon ^{5}}{\ell ^{2}Q^{4}}\right)\)

IBDRE _{MAH}

ω(log2n)

\(\mathcal {O}(n^{6.5+7.5\eta })\)

\(\mathcal {O}(n^{2+3.5\eta })\)

\(\mathcal {O}(n^{2.5+3\eta })\)

\(\mathcal {O}\left (n^{0.5}\right)\)

\(\mathcal {O}\left (\frac {\epsilon ^{2\varphi +1}}{Q^{2\varphi }}\right)\)§

IBDRE _{AFF}

ω(logn)

poly(n)

poly(n)

poly(n)

\(\mathcal {O}\left (n^{0.5}\right)\)

\(\mathcal {O}\left (\frac {\epsilon ^{3}}{\ell ^{4}Q^{2}}\right)\)
