How are these equations equal?

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:

Then author explains that above formula is equal to following when tj=1

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

1 Answer

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

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