1,064 views

1 Answer

0 votes
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

Related questions

1 votes
1 votes
2 answers
1
0 votes
0 votes
2 answers
4