Why is it sloppy? The question of whether you use O or Theta is just that the one gives an upper bound only, and the other one ensures a tight bound (usually ma

Why is it sloppy? The question of whether you use O or Theta is just that the one gives an upper bound only, and the other one ensures a tight bound (usually many people write O, when they mean Theta, which is not wrong, but is also doesn't tell you as much; in the end, it's mostly clear what is intended though). That doesn't mean that you can't use either notation to refer to a worst-case or an average-case (given a suitably defined probability distribution) performance. To say "expected complexity for hash table lookup is O(1)" is neither wrong, nor sloppy.