(S)ETH is a bit of a bummer if you only consider the dominate term in big-O, for the general case.
https://web.stanford.edu/class/cs354/scribe/lecture17.pdf