How would you describe the runtime complexity if I have an algorithm that at each step, the size of the array reduced by an exponentially-increasing amount?
For example, for each step in the algorithm, it is actually processing
n - 2^k items, where
k is the number of steps it has run so far. So for the first step, we process
n - 1 items, the second
n - 2, the third
n - 4, the fourth
n - 8, etc. until the subtracted amount exceeds
n and the algorithm is done.