You are given two sequences a1 a2 an and b1 b2 bn where ea

You are given two sequences, (a_1, a_2, ..., a_n) and (b_1, b_2, ..., b_n), where each sequence consists of distinct integers. Describe a linear time algorithm (in the average case) that tests if a sequence is a permutation of the other. Assume that the simple uniform hashing assumption holds. Explain the running time of your algorithm. \"You are given two sequences, and , where each sequence consists of distinct integers. Describe a linear time algorithm (in the average case) that tests if a sequence is a permutation of the other. Assume that the simple uniform hashing assumption holds. Explain the running time of your algorithm.\"

Solution

Explanation of the running time : We are coutinng how many times each element appearing in each list followed by each element appears exactly the same times in each sequence.