Runtime complexity of algorithm that subtracts progressively larger amounts

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.

It will be: $$T(n,k)=\sum_{i=1}^k n-2^i=kn-\sum_{i=1}^k2^i=kn-(2^{k+1}-1)=kn-2^{k+1}+1$$
If you want something without $$k$$, notice that $$k\le \log(n)$$ since otherwise you will process negative amount of items in some iteration. Then, this means that $$T(n,k)=kn-2^{k+1}+1\le kn \le n\log(n)$$ and hence $$T(n,k)=O(n\log(n))$$.
This is also tight, assuming that $$k$$ is large enough. Indeed, if we assume that $$k=\log(n)$$ then $$2^{k+1}=2n$$, and hence $$T(n,k)=n\log(n)-2n+1=\Theta(n\log(n))$$
Suppose for processing $$n$$ items of your array, you needs $$\mathcal{O}(n)$$ time. Let $$T_k(n)$$ be running time of the algorithm:
$$T_k(n) = \begin{cases} T_{k-1}(n-2^k) + Θ(n-2^k) & \text{ if } n \geq 2^k, \\ 1 & \text{ Otherwise } . \end{cases}$$
Note that $$k=\log n$$ so the number of steps of recursion is at most $$\log n$$.