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)?  
Can this problem be solved in deterministic linear time?


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