アルゴリズムと計算量の問題

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/2$ の $2$ つの部分問題に分けて再帰的に解き、分割と統合に $n$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき、次の漸化式で与えられる。
$$T(1)=1,T(n)=2T\left(\frac{n}{2}\right)+n(n\geqq 2)$$
$T(2^k)$ を $k$ の式で表せ。

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/2$ の $4$ つの部分問題に分けて再帰的に解き、分割と統合に $n^2$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき
$$T(1)=2,T(n)=4T\left(\frac{n}{2}\right)+n^2(n\ge 2)$$
を満たす。$n=2^k$（$k$ は $0$ 以上の整数）のときの $T(n)$ を、$n$ の式で表せ。対数を使う場合は ${\log }_{2}n$ を用いてよい。

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/2$ の $2$ つの部分問題に分けて再帰的に解き、分割と統合に $2n$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき、次の漸化式で与えられる。
$$T(1)=3,T(n)=2T\left(\frac{n}{2}\right)+2n(n\geqq 2)$$
$T(2^k)$ を $k$ の式で求めよ。

ある分割統治アルゴリズム（マージソートの型）は、大きさ $n$ の入力を大きさ $n/2$ の $2$ つの部分問題に分けて再帰的に解き、分割と統合に $n$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき、次の漸化式で与えられる。
$$T(1)=1,T(n)=2T\left(\frac{n}{2}\right)+n(n\geqq 2)$$
$T(2^k)$ を $k$ の式で求めよ。

ある分割統治アルゴリズムは、大きさ $n$ の入力を大きさ $n/2$ の $4$ つの部分問題に分けて再帰的に解き、分割と統合に $n^2+n$ の手間をかける。入力の大きさは $2$ のべき $n=2^k$（$k$ は $0$ 以上の整数）に限って考え、その計算時間 $T(n)$ は
$$T(1)=1,T(n)=4T\left(\frac{n}{2}\right)+n^2+n(n=2^k,k\text{ は正の整数})$$
をみたすとする。$0$ 以上の整数 $k$ に対して、$T(2^k)$ を $k$ の式で表せ。