This is for a sorting algorithm (Merge Sort), where $T$ represents the maximum number of steps executed by the algorithm. $n$ represents the length of the input array (to be sorted) and $k$ represents a threshold, where if $n \le k$, a different algorithm is used to sort which takes $\alpha n^2 + \beta n + \delta$ steps.
If we have a function $T : \mathbb{N}^2 \rightarrow \mathbb{R}$ so that $\forall$ positive integers $n$ and $k$,
$$ T(n,k) = \left\{ \begin{array}{ll} \alpha n^2 + \beta n + \delta & \quad \text{if }\; n \le k \\ T(\lceil n / 2 \rceil, k) + T(\lfloor n / 2 \rfloor, k) + \gamma n + \zeta & \quad \text{if }\; n > k \\ \end{array} \right. $$
And if we know the following:
- $\alpha, \beta, \gamma > 0$
- $\delta + \gamma + \zeta > 0$
- $A = \text{max} \biggl( \alpha + \beta + \delta + \zeta + \gamma, \; k * \alpha + \beta + \frac{1}{k} * (\delta + \zeta + \gamma) \biggr)$
- $B = -(\zeta + \gamma)$
Then we want to prove that
$$T(n,k) \le \gamma n \text{ log}_2 n + An + B$$
for every positive integer $n$.
I thought that maybe I could do proof by induction to prove this. However, then would I have to induct on both conditionals for $T(n,k)$ where I take into account both $n \le k$ and $n > k$? Also, I would assume that I would induct on $n$, but then $k$ remains an unknown variable? Or is induction just not the way to prove this?
I am also confused given the amount of unknown constants in the equations.