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{.}2$ Best$-$Case Asymptotic Runtime

$1$ Point

Grading comment:

What is the best$-$case order of growth for the runtime of g$0$ with respect to

$$

N$?$

Hint: This is a recurrence problem. Find the recurrence and match it to a runtime using methods discussed in lecture.