Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm training to be a software developer and use Stack Overflow a lot, but I'm afraid some basic Maths has gotten in my way. I apologise in advance for a question that may be too easy to be posted here - if so, just tell me!

We're learning about sorting right now, the first of which is a basic selection sort algorithm. Take the following numbers:

$9, 5, 17, 11, 12$

It takes the first number and sets it as the minimum number and compares it to everything after it. As 5 is smaller than it, it swaps the two numbers around and moves on. Next, it takes 5 as the minimum number. If searches the numbers after it and as none are smaller than 5, it stays in position and so on. It effectively works its way from left to right, leaving it sorted as it goes.

Our lecturer has told us that it is sorted in the following way.

To find the smallest, visit n elements + 2 visits for the swap.
To find the next smallest, visit (n-1) elements + 2 visits for the swap.
The last term is 2 elements visited to find the smallest + 2 visits for the swap.

This translates into

$n + 2 + (n-1) + 2 + (n-2) + 2 + \ldots + 2 + 2$

Up until now I'm fine and following it. Then however, he simplifies it to this:

$\displaystyle \frac{n^2}{2} + \frac{5n}{2} - 3$

I have no idea how he has gotten to this. Could anybody explain to me?

share|improve this question
    
$n+(n-1)+(n-2)+\cdots+2$ is the sum of an arithmetic progression with $n-1$ terms, first term $n$, common difference $1$. The other summands in your sum are all twos, and there are $n-1$ of them. –  Gerry Myerson Feb 18 '13 at 23:30
    
I see from looking online that the sum of an arithmetic progression with first term a1 is: Sn = n(a1 + an) / 2 However, I still don't see how I get from that to the simplification (apologies - don't know how to make the formula all neat and tidy like your lettering!) –  Andrew Martin Feb 18 '13 at 23:41
    
The sum of an arithmetic progression with First term $F$, Last term $L$, and Total number of terms $T$, is $T(F+L)/2$. In $n+(n-1)+(n-2)+\cdots+2$, what is the first term? what is the last term? what is the total number of terms? and then what is the sum? –  Gerry Myerson Feb 19 '13 at 0:01
    
Thanks for your help (so far!) –  Andrew Martin Feb 19 '13 at 0:21
    
@GerryMyerson: Simple query. I assume that T(F+L)/2 is a rewriting of: Sn = ½ n [ 2a + (n - 1)d ] (which is what I was using). –  Andrew Martin Feb 19 '13 at 13:13
show 6 more comments

1 Answer

up vote 1 down vote accepted

If we split off every other $2$ we get two different sums: $$2 + 2 + \cdots + 2$$ and $$n + (n - 1) + \cdots + 3 + 2$$

The first is just $2(n - 1)$. For the second we add: $$x = n + (n - 1) + \cdots + 3 + 2$$ with $$x = 2 + 3 + \cdots + (n - 1) + n$$ (add down the columns, so $n + 2, (n - 1) + 3$, etc.) to get $$2x = (n + 2) + (n + 2) + \cdots + (n + 2) + (n + 2) = (n - 1)(n + 2)$$ so $x = \frac{1}{2}(n - 1)(n + 2)$. If you add these two totals together: $$2(n - 1) + \frac{1}{2}(n - 1)(n + 2)$$ you'll get the expression your professor gave you.

share|improve this answer
    
I have to ask - in your second line. Where is the 3 coming from? I thought the last two digits were both 2 (two visits to find the remaining numbers and 2 visits to swap them). I ask because I've worked it out to n2/2 + 5n/2 - 4 : I'm not sure why I'm one out! –  Andrew Martin Feb 19 '13 at 0:07
    
The last $4$ digits of the sum are $\cdots + 3 + 2 + 2 + 2$, when I take away every other two the last two digits are $\cdots + 3 + 2$. When you expand that expression the constant term is definitely $-3$. –  Jim Feb 19 '13 at 0:14
    
Still not fully understanding it, but it's late - I'll keep working away at it tomorrow. Thanks for your help (so far!) –  Andrew Martin Feb 19 '13 at 0:21
    
Can I ask Jim, is this the formula I should be using: ½ n [ 2a + (n - 1)d ] ? –  Andrew Martin Feb 19 '13 at 13:18
    
The reason I ask is that I break down the first line of your answer above to 2(n-1), which becomes 2n - 2. The second part I use the formula for and I do this: n/2(2n + -1(n-1)). I am using n as the first term and -1 as the d (as it is decrementing each time. This simplifies to n/2(2n - n + 1), which becomes n/2(n+1), which becomes n2/2 + n/2. So I get two sums of n2/2 + n/2 and 2n - 2 : I'm obviously making a mistake somewhere - any idea where? (apologies again for not knowing how to format my text) –  Andrew Martin Feb 19 '13 at 13:41
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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