Use the substitution method to prove that the recurrence: T(n) = T(n-1) + theta(n) has the solution T(n) = theta(n2)

Computer Science Aug 29, 2020

Use the substitution method to prove that the recurrence:
T(n) = T(n-1) + theta(n) has the solution T(n) = theta(n2). Please note that this question is in quick sort assignment.

Expert Solution

It easy to notice that T(1) = theta(1) (cost of ordering a one-element array). Then

T(n) = T(n-1) + theta(n)
= theta(n) + T(n-1)
= theta(n) + theta(n-1) + T(n-2)
...
= theta(n) + theta(n-1) + ... + theta(1)
n n
= SUM theta(i) = theta SUM( i )
i=1 i=1

= theta (n * (n + 1)/2) = theta (n^2)

Note, that this kind of behavior for quick sort happens if the input data are (almost) sorted. The behavior of quick sort is then no better than of insertion sort.

Archived Solution

Unlocked Solution

You have full access to this solution. To save a copy with all formatting and attachments, use the button below.

Already a member? Sign In

Important Note: This solution is from our archive and has been purchased by others. Submitting it as-is may trigger plagiarism detection. Use it for reference only.

For ready-to-submit work, please order a fresh solution below.

Or get 100% fresh solution

Get Custom Quote