Q$2$ Recurrence Relations with Case Analysis

$3$ Points

Grading comment:

Consider the following method. Assume k$($N$)$ runs in constant time and returns a bool.

static void g$0($int N$)\{$

if $($N $==0)$

return;

g$0($N $/2)$;

if $($k$($N$))$

g$0($N $/2)$;

$\}$

Q$2\mathrm{.}1$ Best$-$Case Situation

$1$ Point

Grading comment:

In the best$-$case asymptotic runtime analysis for g$0,$ k$($N$)$ always returns false.

Choice $1$ of $2$:True

Choice $2$ of $2$:False