2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.