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

$n$ を $2$ 以上の整数とし、$n$ の関数として次の $8$ 個の計算時間を考える（$\log$ は自然対数、${\log }_2$ は底 $2$ の対数）。
$$f_1(n)=({\log }_{2}n{)}^{{\log }_{2}n},f_2(n)=n^3,f_3(n)=2^{\sqrt{2{\log }_{2}n}},f_4(n)=({\log }_{2}n{)}^5,$$
$$f_5(n)=\left(\genfrac{}{}{0ex}{}{2n}{n}\right),f_6(n)=\sum _{k=1}^n{k}^2\log k,f_7(n)=3^n,f_8(n)={\log }_2(n!)$$
正の値をとる関数 $f,g$ について、$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$ が成り立つことを $f=o(g)$ と書く。
$1$ から $8$ までの番号を並べかえた組 $(i_1,i_2,\dots ,i_8)$ で
$$f_{i_1}=o(f_{i_2}),f_{i_2}=o(f_{i_3}),\dots ,f_{i_7}=o(f_{i_8})$$
がすべて成り立つものがただ $1$ つ存在する。この組 $(i_1,i_2,\dots ,i_8)$ を求めよ。

$n$ を $3$ 以上の整数とし、$n$ の関数として次の $4$ つの計算時間を考える（$\log$ は自然対数）。
$$f_1(n)=n^{100},f_2(n)=2^{\sqrt{n}},f_3(n)=n^{\log n},f_4(n)=(\log n{)}^5$$
これらは、ある並べ方 $f_a,f_b,f_c,f_d$ について
$$f_a=o(f_b),f_b=o(f_c),f_c=o(f_d)(n\to \infty )$$
を満たす。添字の組 $(a,b,c,d)$ を求めよ。ここで $f=o(g)$ は $\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$ を表す。

ある再帰アルゴリズムは、大きさ $n$ の入力を大きさ $\sqrt{n}$ の $2$ つの部分問題に分けて再帰的に解き、分割と統合に ${\log }_{2}n$ の手間をかける。その計算時間 $T(n)$ は、$0$ 以上の整数 $m$ に対して $n=2^{2^m}$ の形の $n$ について
$$T(2)=1,T(n)=2T\left(\sqrt{n}\right)+{\log }_{2}n(n\ge 4)$$
で定められている。

$0$ 以上の整数 $m$ に対し、$T\left(2^{2^m}\right)$ を $m$ の式で表せ。

$p$ を素数、$r$ を正の整数とし、${\mathbb{F}}_p=\{0,1,\dots ,p-1\}$ を $p$ を法とする剰余体とする。キーの集合を $U={\mathbb{F}}_p^r$ とし、$\mathbf{a}=(a_1,\dots ,a_r)\in {\mathbb{F}}_p^r$ に対してハッシュ関数 $h_{\mathbf{a}}:U\to {\mathbb{F}}_p$ を
$$h_{\mathbf{a}}(\mathbf{x})=a_1{x}_1+a_2{x}_2+\cdots +a_r{x}_r({\mathbb{F}}_p\text{での計算})$$
で定める。ただし $\mathbf{x}=(x_1,\dots ,x_r)$ である。

$n$ 個の相異なるキーからなる集合 $S\subseteq U$ を固定し、$\mathbf{a}$ を ${\mathbb{F}}_p^r$ の $p^r$ 個の元から一様ランダムに選ぶ。各 $j\in {\mathbb{F}}_p$ について、バケット $j$ に入るキーの個数を
$$N_j=\left|\{\mathbf{x}\in S:h_{\mathbf{a}}(\mathbf{x})=j\}\right|$$
とおく。このとき
$$E\left[\sum _{j\in {\mathbb{F}}_p}{N}_j^2\right]=n+\frac{n(n-1)}{p}$$
が成り立つことを証明せよ。

ある分割統治アルゴリズムの計算時間 $T(n)$ は、$0$ 以上の整数 $k$ に対して $n=2^k$ のとき、次の漸化式で与えられる。
$$T(1)=1,T(n)=4T\left(\frac{n}{2}\right)+\frac{n^2}{{\log }_{2}n}(n\ge 2)$$
$n=2^k$ の形の $n$ に限って $n\to \infty$ を考えるとき、$T(n)=\Theta (g(n))$ となる関数 $g(n)$ を求めよ。答えは $\Theta$ の中身の式（定数倍を除いた最も簡単な形。例：$n\log n$）で答えよ。