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

# Question 2

## Question 2.1

Here, we can pattern match the recurrence shown with the image of Master theorem above. The values for the constants `a`

, `b`

, and `c`

line up directly with the recurrence shown.

## Question 2.2

$T(n) = \Theta(n^2)$

From the first part of this problem, we identified that `a`

= 2, `b`

= 4, and `c`

= 2.

Plugging into the theorem, we get $\log_b{a} = \log_4{2} = 0.5$, which is less than $c$, which is 2.

Therefore, we are in the first case of the master theorem where our answer follows the form of $\Theta(n^c)$. Our final answer is $\Theta(n^2)$.

# Question 3

## Question 3.1

For the master theorem, a recurrence must follow the format of

Where $a$ measures how many recursive calls are triggered by each method instance: since this method calls `method1`

3 times, $a$ is 3.

$b$ measures the rate of change for input: this method reduces `n`

by half (`n/2`

) when passing it as a parameter to future `method1`

calls, so $b$ is 2.

$c$ measures the dominating term of the non recursive work within the recursive method: Non recursive work in `method1`

is constant, so the dominating term would be 0 == $c$ because $2^0$ == constant work.

## Question 3.2

$T(n) = \Theta(n^{log_2(3)})$