11-2

[wojtask]

(c) Uprościć. Można oprzeć się na pomyśle z https://sites.math.rutgers.edu/~ajl213/CLRS/Ch11.pdf To oszacowanie tam użyte można rozpisać, np.: \binom{n}{k} = \frac{n!}{k!(n-k!)} = \frac{(n-k+1)(n-k+2)\dots n}{k!} Każdy z k czynników z licznika ograniczamy z góry przez n, a mianownik ograniczamy od dołu na podstawie wzoru Stirlinga: k!>(k/e)^k. Zatem \binom{n}{k} < \frac{n^k}{(k/e)^k} = (\frac{ne}{k})^k.

(d) Uprościć. Zainspirować się IM lub https://sites.math.rutgers.edu/~ajl213/CLRS/Ch11.pdf (uważać na drobne błędy). "Dla k = k0 mamy P{k0} \le nQ{k_0} = n · 1/n^3 = 1/n^2." - tu powinno być < w miejscu pierwszej równości. Usunąć zdanie "Udowodnimy teraz ...". Po pokazaniu oszacowania na Q_k, dopisać sens z usuniętego zdania i zakończyć wnioskiem, że to kończy dowód na oszacowanie P_k dla każdego k\ge k_0.

(e) Nowy paragraf od zdania "Aby ..." Usunąć ", że P_k < 1/n^2 dla k \ge k_0" Skrócić wyprowadzenie: \E(X) = k_0\Pr(M \le k_0) + n\Pr(M > k_0) \le k_0\cdot 1 + n\cdot n\cdot P_k < k_0 + 1 = O(\lg n/\lg\lg n).

[wojtask]

Zrobione (c) i (e).

[wojtask]

Zrobione (d).