0
$\begingroup$

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

enter image description here

I need to prove, that

enter image description here

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:

?

$\endgroup$
  • $\begingroup$ We just saw this one, but I can't find the duplicate. $\endgroup$ – Ross Millikan Jan 7 '19 at 15:05
  • $\begingroup$ You just need to induct on $k$. The base case should be $k=1$ Then note that $n\le2^k\implies\left\lceil{ n\over2}\right\rceil\le2^{k-1}$ $\endgroup$ – saulspatz Jan 7 '19 at 15:16
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.