CODEWITHSUNDEEP
big-oquicksort
Adam Burke
Adam Burke

Reputation: 37

Big O time complexity of worst case quick sort?

What I think I understand.
In the worst case the quick-sort algorithm picks the largest or smallest key in list/array to be sorted for every recursive call(if recursive implementation). I understand that the size of n will determine both the number of recursive calls and the number of comparisons(which will decrease by 1 with every step of recursion). So we have n+(n-1)+(n-2)+...+2+1 number of primitive comparison in total.

What I don't understand.
The part I don't quite grasp is how this is O(n^2)? Like I know that it is at least O(n^2) as n+(n-1)+(n-2)+...+2+1 < n^2 but how do I know it isn't say O(n*logn)? Do I have to prove that result to safely confirm it is O(n^2) or is that immediately obvious in a way I can't see? I guess in general how do I know that I have found the lowest function that represents the big O time complexity.

Upvotes: 2

Views: 1047

Answers (1)

Ashot
Ashot

Reputation: 10979

n+(n-1)+(n-2)+...+1 = n(n+1)/2 (you can prove it by mathematical induction), which obviously is O(n^2).

https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

Upvotes: 3

Related Questions