Big O Notation

[tntcoder]

Hi,

Does anyone know any good resources for working out the Big O notation/order of an algorithm? Ive looked around and general information is very patchy/hard to understand.

I mean looking at quick sort or towers of hanoi alogirthms, im struggling to see how to correctly work out the order, and what if/else conditions and different kinds of loops and recursion do to affect the order of the algorithm

Quick sort: O(n^2) (wikipedia)

 function quicksort(q)
     var list less, pivotList, greater
     if length(q) ≤ 1  
         return q  
     select a pivot value pivot from q
     for each x in q
         if x < pivot then add x to less
         if x = pivot then add x to pivotList
         if x > pivot then add x to greater
     return concatenate(quicksort(less), pivotList, quicksort(greater))

Anyone got any advice on learning how to work out the orders? And what each statement does to contribute to the order?

Jack

 

[daz]

I thought Quicksort was O(n log n) on average... hence the name "quicksort".

Wikipedia says this

Formal analysis
From the initial description it's not obvious that quicksort takes O(n log n) time on average. It's not hard to see that the partition operation, which simply loops over the elements of the array once, uses Θ(n) time. In versions that perform concatenation, this operation is also Θ(n).

In the best case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only log n nested calls before we reach a list of size 1. This means that the depth of the call tree is O(log n). But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only O(n) time all together (each call has some constant overhead, but since there are only O(n) calls at each level, this is subsumed in the O(n) factor). The result is that the algorithm uses only O(n log n) time.

 

[Una]

It's n log n on average yeah, n^2 worst case. To analyse quicksort you need to use recurrence relations.