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.
hmmm ... honestly I'm not quite certain what you mean
Are you refering to this part of my post?:
If so:Add columnwise:
Therefore:
When you add columnwise the LHS becomes:
and the RHS becomes:
Since you want to know the value of one s you have to divide by 2. Therefore: