Big O notation for finding duplicates in a list using binary search

Question

I've written an algorithm to find duplicate integers in a sequential list of integers, but I'm running into issues when trying to calculate it's worst case complexity.

Given a sequential list of integers the algorithm is as follows:

1. get the length of the list of integers, assign to list_length - O(1)
2. while list_length is greater than 0: O(n)
  1. remove the item at index 0 from the list and assign to checking - O(1)
  2. set list_length to the current length of the list
  3. perform a binary search of the remaining list for the value assigned to checking - O(log n) where n is the current length of the list
  4. if the item is in the list return True
3. if none of the binary searches found a match return False 

My understanding is that the complexity of a binary search is $O(\log n)$ and if I were not to remove an item from the list on each iteration, the complexity of my algorithm would be $O(n \log n)$ (as I am running an $O(\log n)$ algorithm $n$ times).

What I am not sure of is how the shortening of $n$ will affect the binary search, as on each iteration the complexity of the binary search will change: $O(\log (n - 1))$ on the first iteration, then $O(\log (n - 2))$ on the second.

How do I represent the diminishing size of $n$?

Answer 1

I have two different points:

1. As for complexity of your algorithm I believe this still to be O(N*log N). Consider the first half of the checks. For each check you do a binary search over the list of the size at least N/2 so it is O(log (N/2)) but given that log (N/2) = log(N) + constant it is just O(log N). And you do at least N/2 such checks. So it is O(N*log N)

2. If your list is not sorted, just sorting it to use binary search will take at least O(N*log N) so this is the lower bound anyway. And if it is sorted, your algorithm is very inefficient. You can do it in just O(N) by comparing each 2 sequential elements in the list (duplicates obviously have to be next to each other in a sorted list).

Answer 2

Your running time is $T(n) = \log n + \log (n-1) + \log (n-1) + \dots + \log 1$. As you've observed, this contains $n$ terms, each of which is $O(\log n)$, so $T(n) = O(n\log n)$.

This sum contains $n/2$ terms that are at least $\log(n/2)$, so we have $$T(n) > \frac{n}2\log\frac{n}2 = \frac{n}2\log n - \frac{n}2\log 2 = \Omega(n\log n)\,,$$ and we can conclude that $T(n) = \Theta(n\log n)$.