performance - How to compare two elements in a list in constant time -

suppose have list of elements [5, 3, 1, 2, 4], , want compare 2 elements position. whichever comes first in list greater, or true. so:

compare(5, 3) # true compare(2, 1) # false compare(3, 4) # true 

how can in constant time? 1 way thought of doing using maps, key element , value position in list:

order = {5: 0, 3: 1, 1: 2, 2: 3, 4: 4} 

then have amortized o(1) time, o(n) space. have more elegant solution?

your map idea looks pretty good. fact map o(n) memory shouldn't problem, because can't less o(n) unless use compression techniques (a list o(n) well).

also, since map stores indices of each element, forget original list, , use map. is, unless need list reason. if need insert element middle (say @ position 3), can update map in linear time iterating on element , incrementing necessary indices.

so, map looks efficient solution list basic operations, added awesomeness of o(1) compare function. elegance, map pretty hard beat since doens't require work beyond what's described here.