# Tag Info

If that's the only information you have available, a $\Omega(n)$ lower bound will presumably follow, and presumably this will be the best bound one can hope for in general, as there are plenty of ...