---
# System prepended metadata

title: Untitled

---

## 課題１
### 問題1
1. \begin{align}\ 1 + 2 + 3 + \cdots + n &= \sum_{r=1}^{n} r \\
&= \frac{n(n+1)}{2}
\end{align}


2. $$ O({n^2}) $$

### 問題2
1. \begin{align}\ t(n) = 2^{n} * 2
よりO(2^n) とできる
\end{align}
2. \begin{align}\ t(n) &= {(2^n)}^2 \\ &= 2^n * 2^n \\ &= O(2^n) * O(2^n)
\end{align}
　　　　　　　　　&nbsp;$$となりO(2^n)ではこの関数の時間計算量を表せない$$

### 問題3
1. \begin{align} 
T(n) = 7T(\frac{n}{2}) + \varTheta({n^2})
 &= \varTheta({n^{log_27}}) 
\end{align}
2. \begin{align}\
T(n) &= 8T(\frac{n}{2}) + \frac{an^2}{2} \\ &= \varTheta({n^{log_28}}) \\&= \varTheta({n^3}) 
\end{align}
3. \begin{align}\
T(n) &= 2T(\frac{n}{4}) + \sqrt n + 100
\\ &= 2T(\frac{n}{4}) + O({n^\frac{1}{2}})
\\ &= \varTheta({\sqrt nlog_2{n}})
\end{align}

### 問題4
マージソート

![](https://i.imgur.com/GjMImRJ.png)

選択ソート
![](https://i.imgur.com/ZnqRxHq.png)
$$
\
B = \left(
\begin{array}{cccc}
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0\\
\end{array}
\right)
\
$$
$$
\
C = \left(
\begin{array}{cccc}
0 & 1 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\
\end{array}
\right)
\
$$