def partition(A, l, r): p = A[l] stack = A[l] A[l] = A[r] A[r] = stack s = l for i in range(l, r): if A[i] <= p: stack2 = A[i] A[i] = A[s] A[s] = stack2 s += 1 stack3 = A[s] A[s] = A[r] A[r] = stack3 return s def quicksort(A, l, r): if l < r: q = partition(A, l, r) quicksort(A, l, q - 1) quicksort(A, q + 1, r) return A
I’ve wrote "maybe" quick sort algorithm, as I’ve noticed here the time complexity of partition was O(n) because of the for loop, Also the complexity in quicksort seems to be at least O(n). The question: how is it possible for the entire code to have total time complexity of O(nlogn).
logn comes because of the recursion.
If you call a function recursively you get the complexity of
logn and for each
for inside the function (
for from the partition) you get
logn comes from recursion? Everytime you call that function, inside it you call it again 2 times.
- Calling it once without recursion you call the
forloop 2^0 times / 1 time
- Calling it and getting one time recursion you call
forloop 2^1 times / 2 times (it would be accutally 3 times, but you don’t iterate
ntimes through those
- Calling it and getting 2 times recursion you call
forloop 2^2 times / 4 times