CODEWITHSUNDEEP
algorithmbig-o
user990689
user990689

Reputation: 13

How is Big O of selection sort calculated mathematically?

Can someone please explain in plain English how to calculate it?
I know that you have to visit n+2+(n-1)+2+...+2+2 elements, but how do you get to 1/2n^2 + 5/2n - 3? Thanks!

Upvotes: 0

Views: 1362

Answers (1)

citxx
citxx

Reputation: 2545

n + 2 + (n - 1) + 2 + ... + 2 + 2 is equal to (n + 2) + (n + 1) + ... + 4. It's an arithmetic progression and its sum is calculated as (n + 2 + 4) * (n + 2 - 4 + 1) / 2. It's equal to (n + 6) * (n - 1) / 2 and finally 1/2 * n^2 + 5/2 * n - 3.

f(n) = O(g(n)) means there exists such constant C that f(n) <= C * g(n) for all sufficiently large n. If n is considered as natural number then 1/2 * n^2 + 5/2 * n - 3 = O(n^2) with C = 3/2 for example.

Upvotes: 1

Related Questions