Chapter 4, Problem 63P

Program Plan Intro

Running time of “unique1” and “unique2” algorithms:

As referred to the code fragment 4.7 shows the algorithm for “unique1” and code fragment 4.8 shows the algorithm for “unique2” in the textbook.

• Both these algorithms solve the element uniqueness problem. But the running time of algorithm varies between them.
• The algorithm for “unique1” solves the uniqueness by comparing all the distinct pairs. It uses two nested for loop to find out the duplicates.
• So, it takes the worst-case running time of $O\left(n^2\right)$ to return the unique elements.
• The algorithm of “unique2” solves the uniqueness by placing the duplicate element next to each other.
• It includes a single pass on the array to sort the consecutive duplicates. It takes the worst-case running time of $O\left(n\log n\right)$ time.