The complexity of random ordered structures