#
3.2.3. Selection Algorithm: Complexity Analysis
In
- Theorem
- \forall c, d \in \mathbb{R^+}, if the following recurrence relation holds:
- $T(n) \leq d $ for n \leq 49
- T(n) \leq T(\frac n 5) + T (\frac {3n} 4) + cn for n \geq 50
- then T(n) = O(n)
- Proof
- We want to prove that T(n) \leq kn for some constant k, \forall n \geq 1
- Base case
- T(n) \leq d \leq dn \forall n \geq1
- Therefore, $T(n) \leq kn $ \forall 1 \leq n \leq 49 if we select k such that k \geq d
- Inductive step
- assume that n \geq 5 and T(m) \leq km \forall m < n
- Then, T(n) \leq T(\frac n 5) + T (\frac {3n} 4) + cn
- T(n)\leq k \frac n 5 + k \frac {3n} 4+ cn = \frac {19}{20}kn +cn
- T(n)= kn + (c-\frac k {20})n \leq kn if k \geq 20c
- Base case
- So if we choose k s.t. k = max(d, 20c), T(n) \leq kn for all n \geq 50.
- We want to prove that T(n) \leq kn for some constant k, \forall n \geq 1