The Gateway to Computer Science Excellence

0 votes

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

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)$

52,315 questions

60,432 answers

201,778 comments

95,257 users