Return to Question

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 algorithm for this problem?
Can it be solved faster than sorting them? Can this problem be solved in deterministic linear time?

The answers below conclusively answer this question for many popular models, but not the one I'm looking for: the Turing machine model.

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 algorithm for this problem?
Can it be solved faster than sorting them? Can this problem be solved in deterministic linear time?

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 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 one I'm looking for: the Turing machine model.

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 algorithm for this problem?
Can it be solved faster than sorting them? Can this problem be solved in deterministic linear time?

The answers below conclusively answer this question for many popular models, but not the one I'm looking for: the Turing machine model.

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 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?

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 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 one I'm looking for: the Turing machine model.