Worst-case of q quicksort a Input sorted or reverse sorted a Partition around min or max element a One side of partition al ways has no elements 7(n)=7(0)+7(n-1)+(m) ⊙(1)+7(n-1)+⊙(m) +Q(n) o(n)(arithmetic series)
Worst-case of quicksort Input sorted or reverse sorted. Partition around min or max element. One side of partition always has no elements. T( n) = T(0) + T( n − 1) + Θ ( n ) = Θ(1) + T( n − 1) + Θ ( n ) = T( n − 1) + Θ ( n ) = Θ ( n 2) (arithmetic series )
Worst-case recursion tree 7(n)=7(0)+7(n-1)+cm
Worst-case recursion tree T( n) = T(0) + T( n − 1) + cn T( n )
Worst-case recursion tree 7(n)=7(0)+7(n-1)+cn cn 7(0)7(n-1)
Worst-case recursion tree T( n) = T(0) + T( n − 1) + cn cn T(0) T( n − 1)
Worst-case recursion tree 7(n)=7(0)+7(n-1)+cn cn 7(0)c(n-1) 7(0)7(n-2)
Worst-case recursion tree T( n) = T(0) + T( n − 1) + cn cn T(0) c ( n − 1) T(0) T( n − 2)
Worst-case recursion tree 7(n)=7(0)+7(n-1)+cn cn 7(0)c(n-1) 7(0)c(n-2 ⊙(1)
Worst-case recursion tree T( n) = T(0) + T( n − 1) + cn cn T(0) c ( n − 1) T(0) c ( n − 2) T(0) Θ(1) . .