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

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/ce968165-79db-4910-af25-6aeab61f8417/Untitled.png

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

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d0ca4f5d-d35f-4a16-9e75-2358bbcbb605/Untitled.png

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