Data-structures 2

\begin{matrix} T (n) = 2 T (n - 3) + 2 = \\ = 2^{2} T (n - 3 \cdot 2) + 2^{2} + 2 = \\ = 2^{3} T (n - 3 \cdot 3) + 2^{3} + 2^{2} + 2 = \\ \dots = 2^{i} T (n - 3 i) + 2^{i + 1} - 2 \\ Base case. i = 1 \\ T (n) = 2^{i} T (n - 3 i) + 2^{i + 1} - 2 = 2 T (n - 3) + 2 \\ Induction step. Let T (n) = 2^{i - 1} T (n - 3 (i - 1)) + 2^{i - 1 + 1} - 2 \\ T (n) = 2^{i - 1} (2 T (n - 3 i) + 2) + 2^{i - 1 + 1} - 2 = 2^{i} T (n - 3 i) + 2^{i + 1} - 2 \\ ⟹ \forall 1 \leq i \leq \frac{n}{3} : T (n) = 2^{i} T (n - 3 i) + 2^{i + 1} - 2 \\ T (n) = 2^{n / 3} T (0) + 2^{n / 3 + 1} - 2 = 3 \cdot 2^{n / 3} - 2 \\ ⟹ T (n) = Θ (2^{n / 3}) \end{matrix}

\begin{matrix} T (n) = 2 T (\frac{n}{2}) + n \\ Base case. \forall c \geq 1 : T (1) \leq c \cdot 1^{2} ⟹ T (1) \in O (1) \\ Induction step. Let \forall n^{'} < n : T (n^{'}) = O (n^{' 2}) \\ T (n) = 2 T (\frac{n}{2}) + n \leq \frac{n^{2}}{2} + n \leq 2 n^{2} \\ ⟹ \forall n \geq 1 : T (n) \leq 2 n^{2} ⟹ T (n) = O (n) \end{matrix}

\begin{matrix} T (n) = T (\frac{n}{2}) + T (\frac{n}{3}) + n \\ Base case. \forall c \geq 1 : T (1) \leq c \cdot 1 \\ Induction step. Let \forall n^{'} < n : T (n^{'}) = O (n^{'}) \\ T (n) = T (\frac{n}{2}) + T (\frac{n}{3}) + n \leq \frac{c_{1}}{2} n + \frac{c_{2}}{3} n + n = (\frac{c_{1}}{2} + \frac{c_{2}}{3} + 1) n \\ ⟹ \forall n : T (n) \leq (\frac{c_{1}}{2} + \frac{c_{2}}{3} + 1) n ⟹ T (n) = O (n) \end{matrix}

\begin{matrix} 0 < α < 1 \\ T (n) = T (α n) + T ((1 - α) n) + n \\ Let \forall n^{'} < n : T (n^{'}) = O (n^{'} \log n^{'}) \\ Induction shortcut: \\ T (n) \leq \hat{c} α n \log (α n) + c (1 - α) n \log ((1 - α) n) + n = \\ = \hat{c} α n \log n + \hat{c} α n \log α + c (1 - α) n \log n + c (1 - α) n \log (1 - α) = \\ = c_{1} n + c_{2} n \log n \underset{n \geq 2}{\leq} (c_{1} + c_{2}) n \log n \\ ⟹ T (n) = O (n \log n) \end{matrix}

\begin{matrix} T (n) = 2 T (\sqrt{n}) + \log n \\ Let m = \log n ⟹ n = 2^{m} \\ Let S (m) = T (2^{m}) = T (n) \\ S (m) = 2 S (\frac{m}{2}) + m \\ S (m) = Θ (m \log m) ⟹ T (n) = Θ (\log n \log \log n) \end{matrix}

\begin{matrix} T (n) = T (\sqrt{n}) + 1 \\ m = \log n ⟹ n = 2^{m} \\ S (m) = S (\frac{m}{2}) + 1 \\ \log_{2} (1) = 0 \\ ⟹ By master theorem: S (m) = Θ (m^{0} \log m) = Θ (\log m) \\ ⟹ T (n) = Θ (\log \log n) \end{matrix}