Given a sequence S of n elements, on which a total order relation is defined, describe an efficient method for determining whether there are two equal elements in S . What is the running time of your...

Given a sequence
S
of
n
elements, on which a total order relation is defined,

describe an efficient method for determining whether there are two

equal elements in
S. What is the running time of your method?

Let
S
be a sequence of
n
elements on which a total order relation is defined.

Recall that an

inversion

in
S
is a pair of elements
x
and
y
such

that
x
appears before
y
in
S
but
x
>
y. Describe an algorithm running in

O(nlog
n) time for determining the

number

of inversions in
S.