Get indexes of unique elements in two different arrays in linear time
Given the following assumptions:


Since the meaning of the $=$ operator was not defined, we assume



  $i≠j⇒x_i≠x_j$
  
  ...
  
  The $x_i$ values are not necessarily integers or string, but any type of elements.


are taken to mean that each element of the set simply has a different encoding i.e. is represented by a different number in memory, and that each element is a single word, perhaps a distinct pointer to some arbitrary object.


We assume that, given an arbitrary address, reading/writing at that address takes constant time.
We assume that adding 2 addresses takes constant time.
We assume that a pointer to unbounded memory is available in n time.


Assumptions 2 through 3 hold in most modern system, up to the memory capacity of the system. 4 only considers this program's logical space. 

Then:

Consider the following construction (pseudocode). Note the time complexity, marked by "--":

//Arrays are indexed starting at 1.
//"*x = y" denotes "store y at the address pointed to by x"
//"x = *y" denotes "store the value, at the address pointed to by y, to x"

//Given:
input a1        //pointer to array a1
input a2        //pointer to array a2
input n         //number of elements in set
input mem       //address of unbounded hash table
                  //in the sense of a multitape Turing Machine, 
                  //this points to the first address on "another tape"
output result   //address of n-length array of Tuples

for (t=1; t&lt;=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    hashkey = mem + a2[t] //find an address for this element; is unique
                          //since each element is unique
    *hashkey = t;         //store the index $k_i$ at this address
}

//mem is now a pointer to a (collision free) hash table

for (t=1; t&lt;=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    k = *(a1[t])
    *(result[t]) = Tuple(a1[t], k)
}

return result


...yes this dodges the question by using the suspicious "unbounded hash table". We could be pedantic and argue that the hash table is not technically unbounded on any system we might use, but by this same pedantry we can argue that the lower time complexity bounds of every non-trivial parameterized problem is $O(∞)$ just because we can choose parameters that happen to be too large for the system's address space.

The time complexity of the algorithm, address space permitting, is thus bounded by $T(2n) ∈ O(n)$.