Zaawansowane algorytmy i struktury danych/Ćwiczenia 13

Zadanie ?

Uzasadnić dlaczego algorytm $A_{k+1}$ liczenia minimum dzia"la w czasie $O(1)$ używając $P_{k+1}(n))$

procesor"ow, gdzie $.P_k(n)=n^{1+{ϵ}_k}$

Rozwiazanie

$\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}$