Torbens method is very interesting. At each step it takes O(n) to half the range of inputs. This doesnt say much about how many numbers in the array it removes, but it does say that on average its about half, leading to O(nlogn) expected time. In the worst case it is Quadratic, with one example being [1, 2, 4, 8, 16, 32, 64, ...]
Comments
Torbens method is very interesting. At each step it takes O(n) to half the range of inputs. This doesnt say much about how many numbers in the array it removes, but it does say that on average its about half, leading to O(nlogn) expected time. In the worst case it is Quadratic, with one example being [1, 2, 4, 8, 16, 32, 64, ...]