Chapter 14, Problem 17RE

Explanation of Solution

Comparison:

• Sorting in general will take around $\text{O}\left(\text{n log }\left(\text{n}\right)\right)$ and once the array is sorted another traversal is made to remove the duplicate elements.
• Thus if any duplicates are detected in adjacent thus the remainder of the array needs to moved down and in an average it may require “n/2” steps for the removal of duplicate elements.
• Thus the worst case for the algorithm will be:

$\begin{array}{l}\text{O}\left(\text{n}\text{logn+n}\left(\raisebox{1ex}{$\text{n}$}\!\left/ \!\raisebox{-1ex}{$\text{2}$}\right.\right)\right)\\ \text{=O}\left({\text{n}}^{\text{2}}\right)\end{array}$