$[$ Choose $]$

$[$Choose $]$

the recurrence relation itself rule $3$ of the log rules above the inductive hypothesis the distributive law rule $1$ of the log rules above rule $2$ of the log rules above

Consider the recurrence relation: $T(n)=2T(\frac{n}{2})+n,$ with base case $T(2)=2.$ We want to prove that for $n=2^k$ values, with $k$ an integer at least $1,T(n)=nlgn.$ We will use proof by induction. For this, we will need to use some of the following simple $log$ rules, for $a,c>0$ :

$lo{g}_{a}a=1$

$lo{g}_c(a*b)=lo{g}_{c}a+lo{g}_{c}b$

$lo{g}_c{a}^b=blo{g}_{c}a$

Note, for this class, $lgn=lo{g}_{2}n,$ that is the most common logarithm base we will use. Should it be $($very rarely$)$ needed, $lnn=lo{g}_{e}n,$ the natural log$.$

Below is a proof, but each line has to be justified. So$,$ to start, you have to decide how $($a$)$ should be filled in to justify the base case.

Base case: $T(2)=2=2lg2$ holds because of $($a$).$

Inductive step: assume that $T(n)=nlgn.$ Is it then true that

$T(2n)=2nlg(2n)?$

$T(2n)=2T(n)+2n$ because $of(b).$

$2T(n)+2n=2nlgn+2n$ because $of(c).$

$2nlgn+2n=2n(lgn+1)$ because $of(d).$

$2n(lgn+1)=2n(lgn+lg2)$ because $of(e).$

$2n(lgn+lg2)=2nlg2n$ because $of(f).$

$($a$)$

$($b$)$

$($c$)$

$($d$)$

$($e$)$

$($f$)$

$[$ Choose $]$

is true, and is useful as part of the loop invariant.

is false, and also not close to anything that would be useful as part of the loop invariant.

might not be true, as it suffers from an off$-$by$-$one error, but would otherwise be helpful as part of the loop invariant proof is true, but not useful as part of the loop invariant.

is the exit condition for the loop.

there is no statement here to be true or false.