CODEWITHSUNDEEP
algorithmsortingcode-analysisselection-sort
user7182612
user7182612

Reputation:

How was the running time calculated for this (selection sort) algorithm?

Selection sort algorithm from my book 

When analyzing the the running time for this algorithm, my book used this formula

I understand how the inner summation was simplified to n-1-i. However, I don’t get this final step How was it simplified to [(n-1)n]/2?

Upvotes: 0

Views: 72

Answers (1)

AhmadWabbi
AhmadWabbi

Reputation: 2197

Sigma(n - 1 - i) = Sigma(n) - Sigma(1) - Sigma (i) = (n-1)*n - (n-1) - (n-2)(n-1)/2

Simplify more and you will get nˆ2/2 - n/2 Which give n(n-1)/2

Upvotes: 1

Related Questions