General (negative-weights) adversary bound
The tight SDP characterisation of bounded-error quantum query complexity.
also written:
negative adversary, ADV^pm, gamma_2 with error
Definition
Same SDP as $\mathrm{Adv}$ but the adversary matrix $\Gamma$ may have negative entries. Reichardt proved $\mathrm{Q}(f)=\Theta(\mathrm{Adv}^{\pm}(f))$, so this is not merely a lower bound but a characterisation.
Basic facts
- Perfect composition: $\mathrm{Adv}^{\pm}(f\circ g)=\Theta(\mathrm{Adv}^{\pm}(f)\mathrm{Adv}^{\pm}(g))$, which is how one proves $\mathrm{Q}$ composes.
- Being an SDP, $\mathrm{Adv}^{\pm}$ is computable in time exponential in $n$ but polynomial in the domain size.
Equivalent / near-equivalent measures
- \(\mathrm{Q}_{\varepsilon}(f)\) $\mathrm{Adv}^{\pm}(f) \le \mathrm{Q}(f) = O(\mathrm{Adv}^{\pm}(f))$ Reichardt11 LMRSS11
- \(\gamma_2^{\alpha}(f)\) Equal to the approximate $\gamma_2$ norm of the sign matrix, up to constants LMRSS11
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Adv}^{\pm}(f)\). “\(\mathrm{Adv}^{\pm}(f)\) in terms of it” is the pair with \(\mathrm{Adv}^{\pm}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(\sqrt{n})\) | Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\lambda(f) = \sqrt{n}$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{n})$ here. |
| AND total | \(\Theta(\sqrt{n})\) | Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\lambda(f) = \sqrt{n}$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{n})$ here. |
| PARITY total | \(\Theta(\lceil n/2 \rceil)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \lceil n/2 \rceil$ here. |
| MAJORITY total | \(\Theta(n)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ here. |
| Threshold total | \(\Theta\!\big(\sqrt{k(n-k+1)}\big)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(\sqrt{k(n-k+1)}\big)$ here. |
| Symmetric functions (general) total | \(\Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(\sqrt{n(n-\Gamma(f))}\big)$ here. |
| EXACT-HALF total | \(\Theta(n)\) | Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here. |
| ODD-MAX-BIT total | \(\Theta(\sqrt n)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here. |
| ADDRESS / multiplexer total | \(\Theta(k)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(k)$ here. |
| Binary tree navigation total | \(\Theta(k)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(k)$ here. |
| TRIBES total | \(\Theta(\sqrt n)\) | Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt n)$ here. |
| AND-OR tree (depth 2) total | \(\Theta(n) = \Theta(\sqrt N)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n) = \Theta(\sqrt N)$ here. |
| NAND tree (balanced AND-OR formula) total | \(\Theta(\sqrt{N})\) | Sandwiched: $\lambda(f) \le \mathrm{Adv}^{\pm}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with $\lambda(f) = \sqrt{N}$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt{N})$ here. |
| Recursive MAJORITY-of-3 total | \(\Theta(2^d)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(2^d)$ here. |
| Kushilevitz's function (iterated) total | \(\Omega(\sqrt N),\ O(N)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim; pinning it is the open question about the base function's adversary bound. |
| Rubinstein's function total | \(\Theta(\sqrt N) = \Theta(n)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(\sqrt N)$ here. |
| Ambainis-Sun function total | \(\Omega(\sqrt N),\ O(N^{3/4})\) putative | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so this inherits the \(\mathrm{Q}_{\varepsilon}(f)\) window verbatim. |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^{3/2}) = \Theta(N^{3/4})\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n^{3/2})$ here. |
| Meiburg's tournament-subcube function total | \(\Omega(118.3^{\,d})\) putative | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_{\varepsilon})$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} \ge 118.3^{\,d}$ here. |
| Pointer functions total | \(\widetilde O(n^{1/4})\) | Variant $f_{2m,m}$: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$, so the adversary bound is as small as the algorithm. Reichardt11 |
| Cheat-sheet functions total | \(\widetilde\Theta(n)\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. The adversary bound therefore does see the hardness that $\widetilde{\deg}$ misses -- this is the standard reading of the $\mathrm{Q}$-vs-$\widetilde{\deg}$ separation. Reichardt11 |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n^3)\) | The general adversary bound characterises bounded-error quantum query complexity, $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$, so it inherits the recorded $\mathrm{Q}$. Reichardt11 |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{2/3})\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11 |
| Gilmer-Saks-Srinivasan functions total | \(\Omega(\sqrt n)\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11 |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(n^{1/4})\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11 |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{1/6})\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Reichardt11 |
| Ambainis' exact-quantum function total | \(\Theta(2.1213^d)\) | Squeeze: $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$. Ambainis' lower bound for this family is in fact an adversary bound, so this line is where the recorded $\mathrm{Q}$ comes from. Reichardt11 |
| FORRELATION partial | \(\Theta(1)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = 1$ here. |
| k-FORRELATION partial | \(\Theta(\lceil k/2\rceil)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \lceil k/2\rceil$ here. |
| Simon's problem partial | \(\Theta(n)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(n)$. Against $\mathrm{Adv} = O(1)$ this is the largest known gap between the positive and the general adversary. |
| Deutsch-Jozsa partial | \(1\) | Sandwiched: $\mathrm{Q} \le \mathrm{Adv}^{\pm} \le \mathrm{Q}_E$, with both ends $1$. |
| Bernstein-Vazirani partial | \(1\) | Sandwiched: $\mathrm{Q} \le \mathrm{Adv}^{\pm} \le \mathrm{Q}_E$, with both ends $1$. |
| Two-or-none search partial | \(\Theta(\sqrt n)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$. |
| Marked bit partial | \(\Theta(\sqrt n)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$. The gap to $\mathrm{Adv} = \Theta(1)$ is as wide as the function is hard. |
| Dense marked bit partial | \(\Theta(1)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$. |
| Unstructured search (relation) relation | \(\Theta(\sqrt n)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here. |
| FIND-1 under a density promise relation | \(\Theta(1)\) | Sandwiched between $\mathrm{Q} = \Theta(1)$ and $\mathrm{R} = O(1)$. |
| Approximate Hamming weight relation | \(\Theta(1)\) | Sandwiched between $\mathrm{Q} = \Theta(1)$ and $\mathrm{R} = \Theta(1)$. |
| SearchCNF relation | \(\Theta(1)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$. |
| Gap-Majority partial | \(\Theta(\min(n, 1/\delta))\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$. |
| Gap-Majority at constant gap partial | \(\Theta(1)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$. |
| Parity-labelled FIND-1 partial | \(\Theta(1)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \Theta(1)$. |
| Approximate index partial | \(O(\sqrt{k\log k})\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, hence at most $O(\sqrt{k\log k})$. |
| Collision problem partial | \(\Theta(n^{1/3})\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{1/3})$ here. |
| Element distinctness total | \(\Theta(n^{2/3})\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n^{2/3})$ here. |
| Ambainis-Belovs function partial | \(\Omega(n^{1/3})\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, and here the negative-weight adversary is literally how the lower bound is obtained -- an explicit adversary matrix built from the shifted matchings. AmbainisBelovs23 |
| Ben-David-Kundu total search problems relation | \(\widetilde\Omega(\sqrt n)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, so the negative-weight adversary is $\widetilde\Omega(\sqrt n)$ here while $\widetilde{\deg} = O(\log^7 n)$: for search problems the adversary bound is exponentially stronger than the polynomial method. |
| Yamakawa-Zhandry problem relation | \(\mathrm{poly}(n)\) | $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}) = \mathrm{poly}(n)$; the interest is entirely that this is exponentially below $\mathrm{R}$. |
| Surjectivity total | \(\tilde\Theta(n)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \tilde\Theta(n)$ here. |
| $k$-distinctness total | \(\Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)\)· | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta\!\big(n^{3/4 - 1/(4(2^k-1))}\big)$ here. |
| Triangle finding total | \(\Omega(m),\ O(m^{5/4})\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), so the general adversary inherits the open window verbatim: computing $\mathrm{Adv}^{\pm}(\mathrm{TRI}_m)$ is the triangle problem. |
| Recursive Fourier sampling partial | \(\Theta(2^{\ell})\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(2^{\ell})$ here for the base function $g = g_{\mathrm{mod}3}$. |
| Welded trees relation | \(\Theta(n)\)· | $\mathrm{Adv}^{\pm}$ characterises $\mathrm{Q}$ up to constants (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} = \Theta(n)$ here. Medium confidence on two counts: the characterisation is proved for state conversion rather than for search relations in general, and the $\Omega(n)$ side of $\mathrm{Q}$ is itself folklore. |
| Local search on the hypercube relation | \(\Theta(2^{n/3}n^{1/6})\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(2^{n/3}n^{1/6})$ here. |
| Local search on the grid relation | \(\Theta(k^{d/3})\ (d \ge 6)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)). In the open dimension $d = 4$ the general adversary inherits the window $[\Omega(k^{6/5}), O(k^{4/3})]$ verbatim. |
| Fourier fishing relation | \(\Theta(1)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = 1$ here. |
| Ordered search partial | \(\tfrac1\pi\ln n + O(1)\) | The same ceiling holds for negative weights, so improving $0.221\log_2 n$ needs a genuinely different technique. Unlike the positive-weight $\mathrm{Adv}$ above, this survives the passage to the Boolean decision version, since $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$ and $\mathrm{Q}$ is $\widetilde\Theta(\log n)$ either way. ChildsLee08 |
| Tseitin search on an expander relation | \(O(\sqrt n)\) | $\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$ is settled in the relation setting (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}=O(\sqrt n)$ by Grover search over the $\Theta(n)$ vertices, one of which is always violated. No lower bound is recorded because none is recorded for $\mathrm{Q}$. |
| Inner product mod 2 total | \(\Theta(n)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(n)$ here. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^{3/2}) = \Theta(\sqrt N)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(m^{3/2}) = \Theta(\sqrt N)$ here. |
| Sink of a tournament total | \(\Omega(\sqrt m),\ O(m)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}$ is open between $\Omega(\sqrt m)$ and $O(m)$ here. Pinning this SDP down would settle $\mathrm{Q}(\mathrm{SINK})$. |
| Scorpion graphs total | \(\Omega(\sqrt m),\ O(m)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}$ is only known to lie between $\Omega(\sqrt m)$ (from $\widetilde{\deg}$) and $O(m)$ here. |
| Graph connectivity total | \(\Theta(m^{3/2}) = \Theta(N^{3/4})\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(m^{3/2}) = \Theta(N^{3/4})$ here. |