Hi, i was just wondering if someone could give me some guidance
i am working out the time complexity for quicksort and have got this far
worst -
T(N) = (n-1) + T(1) + T(n-1)
T(n) = (n-1) + (n-2) + T(1) + T(1) + T(n-2)
i no that T(1) = 1
so T(N) = (n-1) + (n-2) +1 + 1 +T(n-2)
but i have no idea here to go from there on!
best -
T(N) = (n-1) + T(n/2) +T(n/2)
T(N) = (n-1) + 2(n/2 -1) + T(N/4) + T(N/4)
T(n) = (n-1) + 2(n/2 -1) + 4(n/4 -1) + T(N/8) + T(N/8)
and once again i dnt no where to go after that
Any help would be greatly appriected
Thanks
Dan
