Polynomial time is pretty bad I feel and not due to any constant factor. A search in a regular database with an index is either O(1) or O(log(N)) depending on the design.