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.
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.
$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)$.
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.
$T(n) = \Theta(n^{log_2(3)})$