SGT Sheet

Question 1

1. $S_{q_0,0}\wedge H_{0,0}$

   Correct

2. $C_{0,0,1}\wedge C_{1,0,1}\wedge C_{2,0,0}\wedge C_{3,0,1}$

   Correct

3. $S_{a,t}\wedge \forall x(x\ne a\to \neg S_{x,t})$ where $t\ge 0$

   Incorrect; $\neg (S_{q,t}\wedge S_{r,t})$ where $q,r$ are states, $q\ne r$ and $t=0,1,\dots ,T$.

4. $S_{q_2,t}$ where $0\le t\le 5$ Expands to: $S_{q_2,0}\vee S_{q_2,1}\vee S_{q_2,2}\vee S_{q_2,3}\vee S_{q_2,4}\vee S_{q_2,5}$

   Correct

5. $S_{q_1,2}\wedge H_{1,2}\wedge C_{1,2,0}\to S_{q_0,3}\vee S_{q_1,3}$

   Correct

Question 2

Using Master Theorem:

The Master Theorem

The Master Theorem states that for some $T(n)$ which is a monotonically increasing recurrence relation such that:

$$\begin{array}{c}T(n)=a\cdot T\left(\begin{array}{c}\lceil \frac{n}{b}\rceil \end{array}\right)+f(n)\\ \text{where }a\ge 1,b\ge 2\end{array}$$

Then we know that:

$$\begin{array}{c}T(n)=\{\begin{array}{ll}\Theta (n^k)& \text{if }f(n)\in O(n^{k-ϵ})\\ \Theta (n^k{\log }_{2}n)& \text{if }f(n)\in \Theta (n^k)\\ \Theta (f(n))& \text{if }f(n)\in \Omega (n^{k+ϵ}){}^{†}\end{array}\\ \text{for some }ϵ>0,\text{where }k={\log }_{b}a\end{array}$$

$\text{† Must satisfy regularity condition, in supplementary reading.}$

Link to original

Identify growth rates of relations: ($n>1$ and $T(1)=1$)

1. $T(n)=4T(\lfloor \frac{n}{2}\rfloor )+n^2$ $a=4,b=2,f(n)=n^2$ $k={\log }_2(4)=2$; hence $f(n)\in \Theta (n^2)$ Growth rate is $\Theta (n^k{\log }_{2}n)=\Theta (n^2{\log }_{2}n)$.

   Correct

2. $T(n)=16T(\lceil \frac{n}{4}\rceil )+n!$ $a=16,b=4,f(n)=n!$ $k={\log }_4(16)=2$; hence $f(n)\in \Omega (n^{2+ϵ})$ Growth rate is $\Theta (n!)$.

   Correct

3. $T(n)=3T(\lceil \frac{n}{3}\rceil )+\sqrt{n}$ $a=3,b=3,f(n)=\sqrt{n}=n^{\frac{1}{2}}$ $k={\log }_3(3)=1$; hence $f(n)\in O(n^{1-ϵ})$. Growth rate is $\Theta (n^k)=\Theta (n)$.

   Correct

4. $T(n)=7T(\lfloor \frac{n}{3}\rfloor )+n^2$ $a=7,b=3,f(n)=n^2$ $k={\log }_3(7)\approx 1.77$; hence $f(n)\in \Omega (n^{0.56+ϵ})$ Growth rate is $\Theta (f(n))=\Theta (n^2)$.

   Correct

Question 3

Consider the following relation:SGT Sheet

$$\begin{array}{rl}T(1)& =1\\ T(n)& =T(n-1)+(3n-2)\end{array}$$

Prove by induction, that $T(n)=\frac{1}{2}(3n^2-n)$ for all $n\ge 1$.

1. Basis Case: LHS: $T(1)=1$ RHS: $$\begin{array}{rl}T(n)& =\frac{1}{2}(3n^2-n)\\ T(1)& =\frac{1}{2}(3\cdot 1-1)\\ & =\frac{1}{2}(2)\\ & =1\end{array}$$ $\therefore$ LHS = RHS
2. Inductive Case: Assume $T(k)=\frac{1}{2}(3k^2-k)$ holds where $n=k$. Hence, try $T(k+1)$: $$\begin{array}{rl}T(k+1)& =T((k+1)-1)+(3(k+1)-2)\\ & =T(k)+3k+3-2\\ & =\frac{1}{2}(3k^2-k)+3k+1\\ & =\frac{1}{2}(3k^2+5k+2)\\ & =\frac{1}{2}((3k^2+6k+3)-(k+1))\\ & =\frac{1}{2}(3(k^2+2k+1)-(k+1))\\ & =\frac{1}{2}(3(k+1{)}^2-(k+1))\text{ as required}\end{array}$$

Correct

Question 4

Consider the following relation:

$$\begin{array}{rl}T(1)& =1\\ T(n)& =8T(\lceil \frac{n}{2}\rceil )+n^3\end{array}$$

Prove by induction, that $T(n)\ge 2n^3$ for all $n\ge 2$.

1. Basis Case: $$\begin{array}{rl}\text{Let }n& =2\\ LHS=T(2)& =8T(1)+2^3\\ & =8+8\\ & =16\\ RHS=2n^3& =2\cdot 2^3\\ & =16\\ \therefore LHS& \ge RHS\text{ as required}\end{array}$$
2. Inductive Case: Assume $T(m)\ge 2m^3$ for all $m\le k$ for some $k\ge 2$. Now substitute $n=k+1$: ( goal is to show $T(n)\ge 2(k+1{)}^3$ ) $$\begin{array}{rl}T(k+1)& =8T\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right)+(k+1{)}^3\\ & \ge 8\cdot 2{\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)}^3+(k+1{)}^3\\ & =2(k+1{)}^3+(k+1{)}^3\\ & =3(k+1{)}^3\\ & \ge 2(k+1{)}^3\text{ as required}\end{array}$$

> [!success] Correct > # Question 5 ```python def f(n): if n <= 1: return 1 else: x = f(math.floor(n / 2)) y = f(math.floor(n / 2)) return g(n, x, y) # runs in linear time O(n) ```

\begin{aligned} T(1) &= 1 \ T(n) &= 2T\begin{pmatrix} \lfloor \frac{n}{2} \rfloor \end{pmatrix} + n \end{aligned}

$$![[TheMasterTheorem]]$$

\begin{aligned} a &= 2 \ b &= 2 \ f(n) &= n \ k &= \log_2 (2) = 1 \ \therefore f(n) &\in \Theta(n) \ \therefore T(n) &= \Theta(n \log_2 n) \end{aligned}