Algorithm for checking if set A is a subset of set B in faster than linear time

Question

Is there an algorithm (preferably constant time) to check if set A is a subset of set B?

Creating the data structures to facilitate this problem does not count against the runtime.

Answer 1

Well, you're going to have to look at each element of A, so it must be at least linear time in the size of A.

An O(A+B) algorithm is easy using hashtables (store elements of B in a hashtable, then look up each element of A). I don't think you can do any better unless you know some advance structure for B. For instance, if B is stored in sorted order, you can do O(A log B) using binary search.