1. ## Algorithm analysis

This is regarding the analysis of a basic computer alogrithm.

It's for a "search sort" alrogrithm. All it does is find the largest number in a list of n elements, places it last and then finds the largest element in the list excluding the last element so each iteration the list has n - 1 elements than before.

T(n) represents the time complexity for the algorithm and c represents the total for other operations.

T(n) = (n - 1) + c + (n - 2) + c ... + 2 + c + 1 + c = n(sqr) / 2 - n / 2 + cn

I can see that this works and that the cn is self explanitory, but how do you get to n(sqr) / 2 - n / 2 part, is there some kind of method or forumla that you work through?

If you want a slightly more detailed explination and example the same promblem on Analysis of algorithms - Wikipedia, the free encyclopedia. Under "run time complexity" on the frst example it says it can be factored as T6[1/2(n(sqr) + n]. Again I can see it works I just don't understand how you get there.

This has been driving me mad for about a week. Any help will be appreciated.

Thanks.

2. Originally Posted by alyosha2
...

T(n) = (n - 1) + c + (n - 2) + c ... + 2 + c + 1 + c = n(sqr) / 2 - n / 2 + cn

I can see that this works and that the cn is self explanitory, but how do you get to n(sqr) / 2 - n / 2 part, is there some kind of method or forumla that you work through?

...
1. Re-write the equation:

$T(n)= (n-1)+(n-2)+(n-3)+...+3+2+1+ \underbrace{c+c+c+...+c+c+c}_{\text{n summands}}$

2. Now take the sum

$s=(n-1)+(n-2)+(n-3)+...+3~~~~~+2~~~~~+1$

Now write the sum in reverse order:

$s=1~~~~~~+~~~2~~~~~+~~~3+...+(n-3)+(n-2)+(n-1)$

$2s=n+n+n+...+n+n+n=n \cdot n$

Therefore: $s = \dfrac12 n^2$

Put all the results together:

$T(n)= (n-1)+(n-2)+(n-3)+...+3+2+1+ \underbrace{c+c+c+...+c+c+c}_{\text{n summands}} = \dfrac12 n^2 + nc$

3. Oh I see, it's just a variation on the normal sum method.

thank you.

Just one more question, why the - n / 2?

4. Originally Posted by alyosha2
Oh I see, it's just a variation on the normal sum method.

thank you.

Just one more question, why the - n / 2?
hmmm ... honestly I'm not quite certain what you mean

Are you refering to this part of my post?:

$2s=n+n+n+...+n+n+n=n \cdot n$

Therefore: $s = \dfrac12 n^2$
If so:

When you add columnwise the LHS becomes:

$s+s=2s$

and the RHS becomes:

$n\cdot n = n^2$

Since you want to know the value of one s you have to divide by 2. Therefore:

$2s=n^2~\implies~s = \dfrac12 n^2$

5. no, your post was very clear. I was meaning in the original algorithm.

T(n) = (n - 1) + c + (n - 2) + c ... + 2 + c + 1 + c = n(sqr) / 2 - n / 2 + cn

It's the same as yours except it has an extra n / 2 subtracted.

6. Originally Posted by alyosha2
no, your post was very clear. I was meaning in the original algorithm.

T(n) = (n - 1) + c + (n - 2) + c ... + 2 + c + 1 + c = n(sqr) / 2 - n / 2 + cn

It's the same as yours except it has an extra n / 2 subtracted.
Earboth's $2s$ is equal to $n-1$ terms each equal to $n$ (he has counted them wrongly), so:

$2s=(n-1)n$

or:

$s=\frac{n^2-n}{2}= \frac{n^2}{2}-\frac{n}{2}$

CB