No, they're not mutually exclusive. But what actually matters in most software is "amortized constant time": linear time worst case only matters in hard real-time systems which can't tolerate any deviation from the expected runtime.

Even algorithms like binary trees can end up with very bad worst cases unless great care is taken in allocating their nodes.