A data structure for lattice representation

In this paper, we present an implicit data structure for the representation of a partial lattice L = (<, N), which allows to test the partial order relation among two given elements in constant time. The data structure proposed has an overall O(n root n)-space complexity, where n is the size of ground set, N, which we will prove to be optimal in the worst case. Hence, we derive an overall O(n root n)-space*time bound for the relation testing problem thus beating the O(n(2)) bottle-neck representing the present complexity. The overall pre-processing time is O(n(2)).