A Recursive Resident Evil problem

Each call makes one recursive call on $N/2$, so the recursion tree is a single chain. Since $N$ is halved at every level, the tree has height $\log N$, which gives $\log N + 1$ levels: level $i = 0$ is the root and level $i = \log N$ is the base case.

At level $i$, the input is $N/2^i$, and the while loop halves $M$ until it reaches $0$. That takes about $\log(N/2^i)$ iterations, so the total work is

Our logs are base 2, so $\log 2 = 1$. Now we evaluate each sum.

First sum: $i$ runs from $0$ to $\log N$, so we add up $\log N + 1$ copies of $\log N$ (one per level):

Second sum: this is an arithmetic sum, so we use $1 + 2 + \dots + k = \frac{k(k+1)}{2}$ with $k = \log N$:

Combining:

Let $X = (\log N)^2$. The leftover $\tfrac{1}{2}\log N$ term is lower order, so it doesn’t contribute asymptotically:

Note: precisely, the while loop runs $\lfloor \log(N/2^i) \rfloor + 1$ times, and the base case does $1$ unit of work. These extra $+1$’s add only $\Theta(\log N)$ in total, so they don’t change the bound.

Alternative solution. Using the quotient rule up front, each level’s work simplifies to $\log\frac{N}{2^i} = \log N - i$. So the levels do $\log N,\ \log N - 1,\ \log N - 2,\ \dots,\ 1$ units of work, and the base case at level $\log N$ does constant work. Reading the tree from the bottom up, this is just an arithmetic sum:

Each call makes two recursive calls on $N/2$, so the number of nodes doubles at every level. The tree has height $\log N$: level $i = 0$ is the root and level $i = \log N$ is the leaf (base case) level, which has $2^{\log N} = N$ nodes.

The work done by a single node depends on whether it is an internal node or a leaf:

Notice that plugging $i = \log N$ into the internal-node formula gives $\log\frac{N}{2^{\log N}} = \log 1 = 0$. That formula counts while loop iterations, but a leaf never reaches the loop: it hits the base case and returns. So the leaves still do $\Theta(1)$ work each, and we count them separately.

Summing over the levels, with $2^i$ nodes at level $i$:

Strategy: Instead of computing the internal-node sum exactly, we trap it between an upper bound and a lower bound. If both bounds grow like the same function of $N$, that function is our Big-$\Theta$ bound. We start with the upper bound.

Upper bound. First, we unravel the $\log\frac{N}{2^i}$ term using log properties. Then we let $X = \log N$, so the upper index $\log N - 1$ becomes $X - 1$:

Next, we change the index. Let $j = X - i$, which rewrites to $i = X - j$. Substituting into each term:

The endpoints change too. Plugging each original endpoint into $j = X - i$:

So $j$ runs from $X$ down to $1$. Since addition is commutative, the order we add the terms in doesn’t matter, so we can swap the endpoints and put $j = 1$ at the bottom of the summation:

We can upper bound $\sum \frac{j}{2^j}$ by letting $j$ run all the way from $1$ to $\infty$. This helps us because adding additional positive terms to a sum only increases the sum:

where $M$ is the resulting sum. Now we find $M$:

How can we massage this to look like a toy geometric series that we’re familiar with? Say,

We know this toy series evaluates to $S = \dfrac{a_1}{1 - r}$, where $a_1$ is the first term of the series and $r$ is the common ratio, provided that $|r| < 1$. Here $a_1 = \frac{1}{2}$ and $r = \frac{1}{2}$:

Now we rewrite $M$. If we take $\frac{1}{2} \cdot M$, every term is cut in half:

But $M - \frac{1}{2} M$ lines up like a classic subtraction problem, where we subtract terms with the same denominator:

This is a geometric series we’re familiar with! With $a_1 = \frac{1}{2}$ and $r = \frac{1}{2}$:

We now revisit the original summation with this new knowledge. We don’t know the exact value of the finite sum, but it is at most the infinite sum $M = 2$:

Finally, we return to summing over the levels, with $2^i$ nodes at level $i$. Calling the total work $T(N)$, the internal-node summation is now upper bounded by $2N$:

So $T(N) \in O(N)$.

Lower bound. We’re not finished (unfortunately) ☹. We need to find a lower bound now. Recall the summations we found by adding up all the work in the recursion tree:

We focus on the first summation. Recall that we were able to massage it with a change of index, which lets us rewrite it as:

Now we find a lower bound for the factor representing the summation, $\sum_{j=1}^{X} \frac{j}{2^j}$:

How does this effectively create a lower bound for us to work with? Every $j$ is at least $1$, so $\frac{j}{2^j} \geq \frac{1}{2^j}$ for every term, and replacing each term with a smaller one can only make the sum smaller. We do this because in rigorous asymptotic analysis, we typically take advantage of lower and upper bounds, and here the lower bound leads us to a finite geometric series:

We’ll apply the same trick we used to find the upper bound (recall $M - \frac{1}{2}M$), but now with respect to $Q$:

Every middle term cancels, leaving only the first term of $Q$ and the last term of $\frac{1}{2}Q$:

So:

Since $2^X = 2^{\log N} = N$, the right-hand side equals $1 - \frac{1}{N}$. Whenever $N \geq 2$, we have $\frac{1}{N} \leq \frac{1}{2}$ (for example, $N = 2$ makes the right-hand side exactly $\frac{1}{2}$). Thus:

Now we multiply both sides of the inequality by $N$. Since $N > 0$, the inequality doesn’t flip:

Tying this back to $T(N)$:

So $T(N) \in \Omega(N)$.

We’ve achieved a lower bound! Since the lower bound and the upper bound are in terms of the same function of $N$,

we have shown that gVirusOutbreak(N) $\in \boxed{\Theta(N)}$.

PHEW!

$\Theta(\log N)$. Even though the tree has about $2N$ nodes, they are never all on the call stack at once. The first call to gVirusOutbreak(N / 2) runs to completion and returns before the second one starts, so the stack only ever holds one root-to-leaf path. That path has $\log N + 1$ frames, and each frame stores only a constant amount of data ($N$ and $M$), so the space used is $\Theta(\log N)$.

Each call makes two recursive calls on $N/2$, so level $i$ has $2^i$ nodes, and the tree has height $\log N$. A node at level $i$ has input $N/2^i$, so its for loop calls the $\Theta(1)$ searchSector method $N/2^i$ times.

At every internal level, the number of nodes doubles while the work per node halves, so each level does the same amount of work:

The leaf level has $2^{\log N} = N$ base-case nodes doing $\Theta(1)$ work each, which is another $\Theta(N)$. Summing over the $\log N$ internal levels plus the leaves:

Unlike gVirusOutbreak, no single level dominates here: every level does the same $N$ work, so the total is (work per level) $\times$ (number of levels).

$\Theta(\log N)$, the same as gVirusOutbreak(N). The for loop changes how much time each call takes, but not how deep the recursion goes. As before, the first recursive call finishes before the second one starts, so the stack only ever holds one root-to-leaf path of $\log N + 1$ frames, each storing a constant amount of data ($N$ and $i$).