Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

You can see a visual explanation of these answers on our awwapp board here.

Question 2

Question 2.1

$$ \frac{n}{4^i} $$

Since every time this function calls itself, it passes in $n/4$, that means that at each level, we divide our input $n$ by 4. So at level $i$, our input size would be $n/4^i$.

Question 2.2

$$ \frac{n}{4^i} $$

The work that each node does at a given level $i$ is determined by the non-recursive parts of the recurrence. In this case, it is the " $+\ n$" which comes after the recursive calls to $T(n/4)$ and changes based the current input size at level $i$. Our answer then is $n/4^i$ work done by a single node on a given non-base case level $i$.

Question 2.3

$$ 3^i $$

There will be $3^i$ nodes at level $i$ because this method produces three more instances of itself every time it recurses.

Question 2.4

$$ 3^i\cdot\frac{n}{4^i} = n\left(\frac{3}{4}\right)^i $$

To evaluate total work per level, we simply multiply the number of nodes per level by the work done by a single node. Answer should be some equivalent of $3^i \cdot \frac{n}{4^i}$

Question 2.5