I have been trying to understand average time complexity of quicksort by going through this link

But I am not able to understand the step where $$\sum_{k=0}^{n-1} Q_k = \sum_{k=0}^{n-1} Q_{n-1-k} $$

How are these two equal?

  • 3
    $\begingroup$ This is just change of variable. You're summing over $Q_0, Q_1, \dots, Q_{n-1}$ in the first sum, and $Q_{n-1}, Q_{n-2}, \dots, Q_1, Q_0$ in the second. $\endgroup$ – stochasticboy321 Oct 17 '15 at 4:18
  • $\begingroup$ ohh.. thanks :) $\endgroup$ – vishnu viswanath Oct 17 '15 at 4:21

Your Answer

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

Browse other questions tagged or ask your own question.