CODEWITHSUNDEEP
algorithmbig-oselection-sort
Jenn
Jenn

Reputation: 1

Summation of Selection Sort

I'm working through the algorithm design manual and stuck on understanding the summation behind selection sort in Chapter 2.

  1. Can someone explain how this summation is simplifed? For example, How do we get to n - i - 1?

  2. if n = 8, then s(n) is (8 - 1) + (8 - 2) + (8 - 3) etc. What does the result of this mean in relation to the formula? I've included a screenshot of the paragrah and my notes for context. screenshot of selection sort

Upvotes: -1

Views: 108

Answers (1)

Neil
Neil

Reputation: 1922

\sum_{i=0}^{j-1} \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{j-1} n - i - 1, why this, where is j?

You were asking about the simplifying step with which the index j is summed over. This link goes more in detail, but in general,

\sum_{j=u}^{v} 1 = -u + v + 1

is equivalent to this pseudo-code,

sum = 0
for(int j = u; j <= v; j++)
    sum += (f(j) = 1)
return sum

For example, with u=3 and v=22, it would be sum = u - v + 1 = 22 - 3 + 1 = 20.

A graphical representation.

With -u + v + 1 at u = i+1 and v = n-1 it simplifies to -(i+1) + (n-1) + 1 = n - i - 1.

if n=8 does \sum_{i=0}^{n-1} n - i - 1 refer to (8-1) + (8-2) + (8-3) + ... + 2 + 1 [+ 0], why two different kinds of values?

It has been simplified from (8-0-1) + (8-1-1) + (8-2-1) + ... (8-5-1) + (8-6-1) + (8-7-1).

Upvotes: 0

Related Questions