The Gateway to Computer Science Excellence
0 votes
60 views

Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.

in Algorithms by | 60 views

2 Answers

+2 votes

Hope, this may helps:)

by
0 votes

Consider n a representative size in your program. Let's say nn is the length of the list you're working with.

The running time, or complexity, of an algorithm is the number of operations you need to do so that your algorithm terminates with an entry data of size nn.

You also have to choose which operations you count, only multiplications, every arithmetic operation, comparsions...
The expression of complexity $C(n)$ is generally obtained by a recursive process.

Let $p(n)$ be $n,n^3,2^n$ or $nlog⁡(n)$ for example

To indicate complexity we use 33 functions, because $C(n)$is not very relevant :

$Ω(p(n)):p(n)<n→∞C(n)Ω(p(n)):p(n)<n→∞C(n)$

$O(p(n)):p(n)>n→∞C(n)O(p(n)):p(n)>n→∞C(n)$

$Θ(p(n)):p(n)∼n→∞C(n)$

Source: https://math.stackexchange.com/questions/1347811/show-that-running-time-of-quick-sort-is-mathcal-on2-when-array-contains-di

by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,432 answers
201,778 comments
95,257 users