Big O notation for finding duplicates in a list using binary search 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$?
I have two different points:


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)
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).