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.

| 60 views

Hope, this may helps:)

by

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

by

+1 vote