Call the array A. A linear time algorithm exists if $\max A = \mathcal O(n)$.

insert the elements of A into a set S.
for every element a in A:
    if S contains x - a:
        return the pair (a, x - a)

This assumes that the set data structure's 'insert' and 'contains' run in constant time. One such data structure is the bit array.

Different data structures yield different running times. If S is a redblack tree, both the first line and the for loop take $\mathcal O(n \log n)$ and you get your bound.

Call the array A. A linear time algorithm exists if $\max A = \mathcal O(n)$.

insert the elements of A into a set S.
for every element a in A:
    if S contains x - a:
        return the pair (a, x - a)

This assumes that the set data structure's 'insert' and 'contains' run in constant time. One such data structure is the bit array.

Different data structures yield different running times. If S is a red-black tree, both the first line and the for loop take $\mathcal O(n \log n)$ and you get your bound.

A linear time algorithm exists. Call the array A.

insert the elements of A into a set S.
for every element a in A:
    if S contains x - a:
        return the pair (a, x - a)

This assumes that the set data structure's 'insert' and 'contains' run in constant time. One such data structure is the bit array. This does not answer your question but I thought it would be useful to share.

Call the array A. A linear time algorithm exists if $\max A = \mathcal O(n)$.

insert the elements of A into a set S.
for every element a in A:
    if S contains x - a:
        return the pair (a, x - a)

This assumes that the set data structure's 'insert' and 'contains' run in constant time. One such data structure is the bit array.

Different data structures yield different running times. If S is a redblack tree, both the first line and the for loop take $\mathcal O(n \log n)$ and you get your bound.