Zaawansowane algorytmy i struktury danych/Ćwiczenia 13

Zadanie ?

Uzasadnić dlaczego algorytm $A_{k+1}$ liczenia minimum działa w czasie O(1) używając $P_{k+1}(n))$ procesor"ow, gdzie $P_k(n)=n^{1+{ϵ}_k},{ϵ}_k=\frac{1}{2^k-1}$

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