As discussed earlier in Section REF , the complexity of the original \(d\) -dimensional problems \(Q {\bf w}\)  and \(\hat{Q} {\bf w}\)  reduces to several smaller one-dimensional
problems of either \(Q^{(k)} {\bf z}\)  or \(\hat{Q}^{(k)} {\bf z}\)  form, given by (REF ).
We now study the complexity of computing one-dimensional
problems to obtain \(\text{cost}(Q^{(k)} {\bf z})\) .
We follow [1]} and assume \(n_k = 2^q\) , where \(q\)  is a
non-negative integer that may be different for different \(k\) .
Let \({\mathcal {H}}_q\)  denote the family of \(2^q \times 2^q\) 
hierarchical matrices constructed above.
Corresponding to the quadtree block
structure, the representation of \({\mathcal {H}}_q\)  for \(q \ge 1\)  can be given recursively,
\({\mathcal {H}}_q =\left(\begin{array}{@{}c|c@{}}{\mathcal {H}}_{q-1}& {\mathcal {N}}_{q-1}\\\hline {\mathcal {N}}_{q-1}^*& {\mathcal {H}}_{q-1}\end{array}\right),\qquad {\mathcal {N}}_q =\left(\begin{array}{@{}c|c@{}}{\mathcal {R}}_{q-1}& {\mathcal {R}}_{q-1}\\\hline {\mathcal {N}}_{q-1}& {\mathcal {R}}_{q-1}\end{array}\right),\) 
