Deadline: 2022-06-22 22:22 (196 days ago)
Pavel Veselý — 2022-05-06 10:58 (244 days ago) — reply
Vyřešte jednu z následujících rekurencí časové složitosti, v nichž vždy máme $T(1) = 1$:
1. $T(n) = T(n/3) + T(n/7) + \Theta(n)$ [7 bodů]
2. $T(n) = T(\beta_1 n) + T(\beta_2 n) + \dots + T(\beta_a n) + \Theta(n)$
pro konstanty $a\in \mathbb{N}$ a $\beta_i > 0$ splňující $\sum_{i=1}^a \beta_i \le 1$ [10 bodů]
3. $T(n) = T(\beta_1 n) + T(\beta_2 n) + \dots + T(\beta_a n) + \Theta(n^c)$
pro konstanty $a\in \mathbb{N}$, $c > 0$ a $\beta_i > 0$ [15 bodů --- jde o bonus v bonusovém úkolu]
(Všimněte si, že každý další případ pokrývá ten předchozí. Pro jednoduchost s nemusíte zabývat zaokrouhlováním na celá čísla.)