how to tell if code is written in O(NlogN) in C

Question

Given an array of N elements, you notice that there are some duplicate values. Implement a modified merge function such that the mergesort code we saw in class both sorts the array and removes all duplicates from the array. Your algorithm should run in O(N log N) time; briefly argue/justify that your program runs in O(N log N) time.

Answer 1

Yes — this works cleanly by running MergeSort as usual to sort the array, and then filtering out duplicates during the merge step. The key observation is that after sorting, equal values appear next to each other, so when writing into the merged output, you only write a value if it is different from the last value you wrote.

Answer 2

Though Alfred gave you a good idea of what to do, the justification was missing.

To have an O(n log(n)) complexity of your final algorithm, you cannot make drastic changes compared to the base merge sort, that already has an O(n log(n)) time complexity. The complexity is measured in terms of comparisons.

The idea here is that we only need to add one more comparison every time we'd decide to write the next element, and this only changes the time complexity a constant time to O((n + 1) * log(n)), but for high n, the constants become insignificant, so it remains O(n log(n)).