0
$\begingroup$

I am reading CLRS 3rd edition(Wikipedia page) on page 26, author deduced a formula for the running time of insertion sort and that is: enter image description here

Then author explains that above formula is equal to following when tj=1 enter image description here

Can anyone explain how are these equations equal, especially the terms having c5 and c6? Also why c6 is missing?

$\endgroup$
1
$\begingroup$

If you assume that $t_j$ is $1$ for all $j$, then $\sum_{j=2}^{n}{(t_j - 1)} = 0$, thus $c_6$ and $c_7$ cancel out, and $\sum_{j=2}^{n}{t_j} = \sum_{j=2}^{n}{1} = n - 1$.

Therefore, you obtain the desired formula.

Edit (more details): Assume $t_j$ = 1 for all $j$,

$$ c_1n + c_2(n-1) + c_4(n-1) + c_5\sum_{j=2}^{n}{t_j} + c_6\sum_{j=2}^{n}{(t_j - 1)} + c_7\sum_{j=2}^{n}{(t_j - 1)} + c_8(n-1)$$ $$ c_1n + c_2(n-1) + c_4(n-1) + c_5\sum_{j=2}^{n}{1} + c_6\sum_{j=2}^{n}{(1 - 1)} + c_7\sum_{j=2}^{n}{(1 - 1)} + c_8(n-1) $$ $$ c_1n + c_2(n-1) + c_4(n-1) + c_5\sum_{j=2}^{n}{1} + c_6\sum_{j=2}^{n}{0} + c_7\sum_{j=2}^{n}{0} + c_8(n-1) $$ $$ c_1n + c_2(n-1) + c_4(n-1) + c_5(n-1) + 0 + 0 + c_8(n-1) $$ $$ c_1n + c_2(n-1) + c_4(n-1) + c_5(n-1) + c_8(n-1) $$ $$ (c_1 + c_2 + c_4 + c_5 + c_8)n - (c_2 + c_4 + c_5 + c_8) $$

$\endgroup$
  • $\begingroup$ What about term having c5? How did it get (n-1)? $\endgroup$ – user3461957 Aug 9 '15 at 12:01
  • $\begingroup$ @user3461957, I have added details. Is it clear now? $\endgroup$ – 永劫回帰 Aug 9 '15 at 12:34

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.