Zaawansowane algorytmy i struktury danych/Ćwiczenia 13

Zadanie 1

Uzasadnić dlaczego algorytm $A_{k+1}$ liczenia minimum dzia"la w czasie $O(1)$ używając $P_{k+1}(n))$ procesor"ow, gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Uzasadnienie pozostawiamy jako "cwiczenie.P_k(n)= n^{1+\epsilon_k} }

Rozwi"azanie

$\max \{(\frac{n}{n^{\alpha }}{)}^{1+{ϵ}_k},\frac{n}{n^{\alpha }}\times (n^{\alpha }{)}^{1+{ϵ}_k}\}=O(P_{k+1}(n))$

gdzie $\alpha=\frac{1}{2^{k}+1}$