I have been at this problem for a while now, and I cannot wrap my head around it. Any kind of help would be greatly appreciated!
The runtime for a sorting algorithm can be described by $a_{1} = 3$ and
I need to prove, that
For all $n, k \in Z^{+}$
I've tried to do the basestep, but even here I'm not sure if it's correct. I hope someone can help with the induction step as well.
Basecase:
$n, k = 2$
$a_{2} =a_{2/2} + a_{2/2} + 3*2+1 = 13 $
$3* 2 * 2^2 + 4 * 2^2 -1 = 39$
$a_n \leq 3 * k * 2^k + 4 * 2^k - 1$ applies for the basebase, since $13 \leq 39$ is true.
Inductionstep:
?
Try to prove by induction over $k$ that for all $1 \leq n \leq 2^k$, $a_n \leq 3k2^k+2^{k+2}-1$.