CODEWITHSUNDEEP
arraysdata-structuresquicksort
Basla Azhar
Basla Azhar

Reputation: 5

dry run of worst case of quick sort

we know that in quick sort worst case is O(n^2) i can solving the array of:

1 2 3 4 5 6 7 8 9 10

when i put value of n in equation of worst case answer is 100 but in dry run it can solve in 51 steps. its a big difference what the reason of this

Upvotes: 0

Views: 157

Answers (2)

Anna
Anna

Reputation: 21

It would be helpful to consider the definition of Big O when thinking about how it can be applied, in this case, to the worst case scenario in a quick sort algorithm. The Big O describes the asymptotic behavior of functions. When referring to an algorithm, the running time is bounded above by f(x) which is O(f(x)). What this means is that your algorithm cannot grow any faster than f(x). In your example, quick sort is bounded above by (n^2), therefore, it cannot grow any faster than n^2 as n gets arbitrarily large.

Being bounded above by n^2 does not necessarily mean the worst case takes exactly n^2 steps. It is also bounded above by n^4, n^100, n^n. All this means is that quick sort can never grow faster than n^2, n^4, n^100, n^n.

Another point to keep in mind when describing Big O is thinking in terms of n getting arbitrarily large or going towards infinity. In this example n is 10, but when you consider the Big O of larger values of n in the worst-case the number of steps will increase, but will never exceed n^2. I hope this helps!

Upvotes: 0

Sergiocon
Sergiocon

Reputation: 19

O(n^2) means that the complexity grows with the square of n, not that it is exactly n^2.

You need to check how the cost (ans) grows when n grows. Try putting 5, 10 and 20 items in the worst-case array and then you will see that ans does not grow proportionally (2x each time) to n but much faster.

Upvotes: 2

Related Questions