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)
Anyone got any advice on learning how to work out the orders? And what each statement does to contribute to the order?
Jack
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)
Code:
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