The recognition complexity of ordered set properties is considered, i.e. how
many questions have to be asked to decide if an unknown ordered set has a
prescribed property. We prove a lower bound of Ω (n²) for properties that are
characterized by forbidden substructures of fixed size. For the properties
being connected, and having exactly k comparable paris we show that the
recogintion complexity is (n:2); the complexity of interval orders is exactly
(n:2) -1. Non-trivial upper bounds are given for being a lattice, containing a
chain of length k ≥ 2 and having width k.