My professor said that it can't happen a(n)=O(b(n)) and at the same time: b(n)=O(a(n)) but why is that? according to the definition there is no contradiction at all.

The first says from some point a(n)<= alpha * b(n) and the second says from some other point b(n)<= beta * a(n)

CodePudding user response：

This is not correct. Because it is an alternative definition of Theta notation. Hence, if a(n) = O(b(n)) and b(n) = O(a(n)), we will have a(n) \in Theta(b(n)) and vice versa. For example, a(n) = b(n) = n. So, a(n), b(n) \in O(n). Hence, a(n) \in O(b(n)) and b(n) \in O(a(n)).

However, note that if we have o (little-oh) in replace of O (big-oh), the claim is correct!