Consider the following problem:

**Input:** two arrays $A$ and $B$ of length $n$, where $B$ is in sorted order. 

**Query:** do $A$ and $B$ contain the same items (with their multiplicity)?

What is the fastest [deterministic][1] algorithm for this problem?  
Can it be solved faster than sorting them ($O(n \lg n)$ time, or $O(n \lg\lg n)$ (see Yuval's comment))?
Can this problem be solved in deterministic linear time?

The answers below conclusively answer this question for many popular models, but not the right one. I'm not an expert on models, but consider the statement "It has not been proven if (some) NP problems require more than O(n) time". If they were using the model of Yuval's popular answer below using the comparison model, that statement would be wrong, but the statement is considered correct. So what model are they using when they say that?

  [1]: https://en.wikipedia.org/wiki/Deterministic_algorithm