skanev/playground — pull request #1 by ericberens (2014-05-01 12:59:40+00:00)
Title: Update 02.markdown

Based on your pseudocode...

SELECTION-SORT(A):
for i = 1 to A.length - 1 n-1
min = i 1
for j = i + 1 to A.length n-2 + ...
if A[j] < A[min] 1
min = j 1
temp = A[i] 1
A[i] = A[min] 1
A[min] = temp 1
__________
(n-1) + (n-2) + ... + 6

Since this is a simple arithmetic progression (see also http://en.wikipedia.org/wiki/Arithmetic_progression), it can be simplified to

(n(n-1))/2 -> (n^2 - n)/2 -> 1/2(n^2) - 1/2(n)

Dropping everything except the highest order we get O(n^2) and not O(n) for both best and worst cases.

This could have been a minor typo but figured I provide an explanation.