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$?