operates in constant time for the same reason; otherwise it uses at most $|s_\ell| \lg \sigma_\ell
     + {\ensuremath{\mathcal{O}\left( {\frac{|s_\ell| \lg \sigma_\ell}{\lg \lg \sigma_\ell}} \right)}}
\leq |s_\ell| \lg \sigma_\ell
     + {\ensuremath{\mathcal{O}\left( {\frac{|s_\ell| \lg \sigma_\ell}{\lg \lg \lg n}} \right)}}$ bits (the latter because $\sigma_\ell > \lg n$). Thus in all cases the space for $s_\ell$ is bounded by $|s_\ell| \lg \sigma_\ell + o(|s_\ell| \lg \sigma_\ell)$ bits.[^3] Finally, since ${\ensuremath{{M}}}$ is a sequence of length $\sigma$ over an alphabet of size $\lceil \lg^2 n \rceil$, the wavelet tree for ${\ensuremath{{M}}}$ takes at most ${\ensuremath{\mathcal{O}\left( {\sigma \lg \lg n} \right)}}$ bits. Because of the property we referred to in the beginning of this section, $nH_0(s) \ge (\sigma-1)\lg n$, this space is also $o(nH_0(s))$. By these calculations, the space for $T$, ${\ensuremath{{M}}}$ and the $S_\ell$’s adds up to $nH_0(s) + o(nH_0(s)) + o(n)$. Depending on which time tradeoff we use for Golynski et al.’s data structure, we obtain the results of Table \[tab:previous\]. We can refine the time complexity by noticing that the only non-constant times are due to operating on some string $s_\ell$, where the alphabet is of size $\sigma_\ell < 2^{1/\lg n}|s_\ell|/{\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}$, where $a$ is the character in question. Thus 