Is there a typo in this runtime analysis of selection sort?

88 Views Asked by At

This is from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf, slide 6.

The instructor is doing a runtime analysis of selection sort. Here is what he has

enter image description here

From step 1 to step 2, is there a typo?

From what I worked out

(N-1 - (i + 1) + 1) Should evaluate to (N-1 - i - 1 + 1) which evaluates to (N - i - 1) not (N-1 + 1). Or am i missing some step in the summation

1

There are 1 best solutions below

1
On BEST ANSWER

You are correct. The last line should read $$ \sum_{i=0}^{N-1} (N - i -1). $$

The next line of the slide also has an error: rather than $$ N\sum_{i=0}^{N-1} 1 - \sum_{i=0}^{N-1} i, $$ it should read $$ N\sum_{i=0}^{N-1} 1 - \sum_{i=0}^{N-1} (i + 1) \qquad \text{or} \qquad N\sum_{i=0}^{N-1} 1 - \sum_{i=1}^{N} i $$ and the concluding equality should be $$ N^2 - \frac{N(N+1)}{2}, $$ or simply $$ \frac{N(N-1)}{2}. $$

Probably the author is being rather sloppy since they only care about the asymptotic size (the big-O time) so in the end, none of this matters.