Background

I am currently taking an Algorithm and Analysis course and doing some extra studying on my own from the text book. This is not a homework question or exercise even. I am just trying to understand completely how the authors are doing the combining of terms in the time/cost equation for Insertion-Sort.

I understand what is being shown up until we get to the actual equation. I understand that each line, barring the comment which is considered to not have a cost, has a constant cost c.

This is how they have broken down the time/cost for the algorithm in psuedo-code:

1. for j = 2 to A.length
2.     key = A[j]
3. //Insert A[j] into the sorted
4.      sequence A[1..j - 1]
5. i = j - 1
6. while i > 0 and A[i] > key
7.     A[i + 1] = A[i]
8.     i = i - 1
9. A[i + 1] = key

Here's the cost/time for each line according to textbook:

1. $c_1n$
2. $c_2(n-1)$
3. 0
4. 0
5. $c_4(n - 1)$
6. $c_5 =\sum\nolimits_{j}^{n} 2t$
7. $c_6=\sum\nolimits_{j}^{n} 2{t - 1}$
8. $c_7=\sum\nolimits_{j}^{n} =2{t - 1}$
9. $c_8(n - 1)$

The best case run time of the algorithm is then given by:

$$T(n) = \ c_1(n) + c_2(n - 1) + c_4(n - 1) + c_5(n - 1) + c_8(n - 1)$$

This is where I get confused. Somehow they combine all of these terms to simplify the equation but it's done in one step so I can not follow/reproduce it on my own. This is what they come up with:

$$= (c_1 + c_2 + c_4 + c_5 + c_8)n - (c_2 + c_4 + c_5 + c_8)$$

According to the author it can be expressed as $an + b$ and thus a linear function of $n$. As mentioned above, I don't know how they simplified the equation nor how it can be expressed as $an + b$. I do understand that it is in linear equation form. How do I make the leap or bridge the gap per say?

• The best case is observed when the array is already sorted (non decreasing order) , in this case the 'inner while' loop executes only once for each iteration of 'for' loop . for example 5. c5∑2t the value of t becomes 1 and summation becomes linear in n. Can you take it from here? – Shubham Singh rawat Oct 3 '16 at 18:59
• From the first highlighted equation, just do the multiplication by all the constants and regroup them. From the second equation, let $a=c_1+c_2+c_4+c_5+c_8$ and do the same thing for $b$. – Rick Decker Oct 3 '16 at 19:29
• I'm voting to close this question as off-topic because it is about elementary algebra, not computer science. – David Richerby Oct 4 '16 at 7:47
• @ShubhamSinghrawat The question is purely about how to simplify the first yellow formula into the second one. Everything before the first yellow formula is just context. – David Richerby Oct 4 '16 at 7:48
• @David but wouldn't that be a trivial simplification? – Shubham Singh rawat Oct 4 '16 at 10:35

The time complexity of the insertion sort is O(n2) in the worst case(array in decreasing order) and O(n) in the best case(array in non decreasing order). These bounds result from the variance in the number of iterations of the inner while loop or in other words the while loop dominates the running time of the algorithm. Considering the number of iterations while loop makes in different cases can be summarized as follows :

c5 = ∑nj 2t

In the best case : where while loop finds the condition A[i] > key as true in the first iteration itself the t evaluates to 1 and thus the summation evaluates to O(n) . Therefore you see a constant term multiplied by n in the best case expression for T(n). Also there are no shifts required therefore the terms for line number 7 and 8 become zero and you don't see the constant terms c6 and c7 in the final expression for T(n) in the best case. (c6=∑nj2(t−1) , substituting t = 1 makes the summation 0.)

In the Worst case : the while loop has to make n-1 iterations in the worst case iterations to find a value A[i] > key . The value of t becomes n-1 and the summation evaluates to O(n2).

The question about T(an+b) : 'a' is nothing but a constant a >= c1+c2+c4+c5+c8

I suspect it is not the algebraic simplification which you are confused about and i have made my point clear.

• I apologize for the dispute, however I do still feel it was a valid question. Perhaps though it may have been asked in the wrong community though I do not believe that it belongs in a math community. – user90376 Oct 12 '16 at 6:06
• Accidently hit 'enter' and I can not seem to edit that comment so that's why there is a double post here. – user90376 Oct 12 '16 at 6:07

So you question is how to go from:

T(n)= c1(n)+c2(n−1)+c4(n−1)+c5(n−1)+c8(n−1)


to

T(n)= (c1+c2+c4+c5+c8)n−(c2+c4+c5+c8)


Step 1 (Expand the statement):

T(n)= c1(n)+c2(n)−c2+c4(n)−c4+c5(n)−c5+c8(n)−c8


Step 2 (Group similar elements):

T(n)= c1(n)+c2(n)+c4(n)+c5(n)+c8(n)−c2-c4-c5-c8


Step 3 (Find the factors):

T(n)= (c1+c2+c4+c5+c8)n−(c2+c4+c5+c8)

• this doesn't seem to be what the question demands. You fist need to substitute values of c5,c6 etc from the cost terms for each line and then arrive at the best case – Shubham Singh rawat Oct 3 '16 at 19:52
• @ShubhamSinghrawat. No. The cost terms are constants, so there are no possible choices to make in this answer to get best (or worst) case answers. – Rick Decker Oct 4 '16 at 0:35

You might be confusing $c_1(n)$ to a function application: the function $c_1$ applied to $n$. However, here it just means the constant $c_1$ multiplied by the variable $n$. Given this, the simplification in the formula for $T(n)$ is simple algebra. Rendering the resulting expression in the form $an+b$ is also simple algebra.