Sure, asymptotic time complexity only says anything about the asymptotic behavior. On the other hand, I have had far more cases of things blowing up due to cubic or even quadratic time complexities than I have for linear; linear is what you expect, if it takes a long time for a toy input, it'll take twice as long for a real input at double the size. Not so with the superlinear ones, your toy problem might work fine, but cubed? Ain't happening this millennium. This combined with the constant factor tending to also grow as the problem size grows really is a potent foot-gun.