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