CODEWITHSUNDEEP
algorithmquicksort
malhobayyeb
malhobayyeb

Reputation: 2881

Analyzing the QuickSort algorithm

I am following an MIT lecture on YouTube about Quick Sort. I got most of the idea but I am stuck of what he said Arithmetic Series in the following point:

Worst-Case: T(n) = T(n-1) + Theta(n)

He asked, "What is that equals to?"

And then he said it is equal to Theta(n^2)

Why is it equal to Theta(n^2) and not equal to Theta(n)??

Upvotes: 1

Views: 375

Answers (1)

amit
amit

Reputation: 178521

It is a sum of arithmetic progression T(n) = T(n-1) + n = n + n-1 + n-2 + ... + 1 = n(n+1)/2 which is in Theta(n^2)

You can also get it with induction, assuming Theta(n) stands for n (for simplicity, can be modified using the same approach):

Hypothesis: T(n) = n(n+1)/2
Base: T(1) = 1*2/2 = 1
Step: 
T(n) = T(n-1) + n <= (*) (n-1)*n/2 + n = 
     = (n^2 -n)/2 + 2n/2 = (n^2-n + 2n)/2 =
     =  (n^2 +n) /2 = n(n+1)/2
(*) induction hypothesis

This shows us T(n) = n(n+1)/2 which is indeed in Theta(n^2).

Upvotes: 4

Related Questions