Skip to main content
Computer Science

Return to Question

added 29 characters in body; edited tags; edited title
Source Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Selection Sort Time Complexity usingruntime in terms of Big O notation

I'm trying to understand why the sorting algorithm Selection Sort has a time complexity of O(n^2)asymptotic runtime in $O(n^2)$.

Looking at the math, the time complexityruntime is

T(n) = (n-1) + (n-2) + ..$\qquad T(n) = (n-1) + (n-2) + \dots + 2 + 1$. + 2 + 1

And this is stated to be equal to

O(n^2)$\qquad O(n^2)$.

However I just don't understand the intuition. I have tried several practical experiments for n=10 up to n=5000, and all point to that the time complexity of e.g. 5000 can never be greater T(5000) = 12.497.500 -- not T(5000) = 5000^2 = 25.000.000.

Now, I know that 5000 is not the same as infinity, but I just don't understand the intuition behind

(n-1) + (n-2) + ..$\qquad (n-1) + (n-2) + \dots + 2 + 1 = O(n^2)$. + 2 + 1 = O(n^2)

Does someone have a great pedagogical explanation that my dim-witted mind can understand?

Selection Sort Time Complexity using Big O notation

I'm trying to understand why the sorting algorithm Selection Sort has a time complexity of O(n^2).

Looking at the math, the time complexity is

T(n) = (n-1) + (n-2) + ... + 2 + 1

And this is stated to be equal to

O(n^2)

However I just don't understand the intuition. I have tried several practical experiments for n=10 up to n=5000, and all point to that the time complexity of e.g. 5000 can never be greater T(5000) = 12.497.500 -- not T(5000) = 5000^2 = 25.000.000.

Now, I know that 5000 is not the same as infinity, but I just don't understand the intuition behind

(n-1) + (n-2) + ... + 2 + 1 = O(n^2)

Does someone have a great pedagogical explanation that my dim-witted mind can understand?

Selection Sort runtime in terms of Big O

I'm trying to understand why the sorting algorithm Selection Sort has asymptotic runtime in $O(n^2)$.

Looking at the math, the runtime is

$\qquad T(n) = (n-1) + (n-2) + \dots + 2 + 1$.

And this is stated to be equal to

$\qquad O(n^2)$.

However I just don't understand the intuition. I have tried several practical experiments for n=10 up to n=5000, and all point to that the time complexity of e.g. 5000 can never be greater T(5000) = 12.497.500 -- not T(5000) = 5000^2 = 25.000.000.

Now, I know that 5000 is not the same as infinity, but I just don't understand the intuition behind

$\qquad (n-1) + (n-2) + \dots + 2 + 1 = O(n^2)$.

Does someone have a great pedagogical explanation that my dim-witted mind can understand?

Tweeted twitter.com/#!/StackCompSci/status/413394567527149568
Source Link
Pætur Magnussen
Pætur Magnussen
  • 171
  • 1
  • 1
  • 3

Selection Sort Time Complexity using Big O notation

I'm trying to understand why the sorting algorithm Selection Sort has a time complexity of O(n^2).

Looking at the math, the time complexity is

T(n) = (n-1) + (n-2) + ... + 2 + 1

And this is stated to be equal to

O(n^2)

However I just don't understand the intuition. I have tried several practical experiments for n=10 up to n=5000, and all point to that the time complexity of e.g. 5000 can never be greater T(5000) = 12.497.500 -- not T(5000) = 5000^2 = 25.000.000.

Now, I know that 5000 is not the same as infinity, but I just don't understand the intuition behind

(n-1) + (n-2) + ... + 2 + 1 = O(n^2)

Does someone have a great pedagogical explanation that my dim-witted mind can understand?