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