In the process of quicksorting n elements, the worst-case time complexity is

cuizhe0817 注册会员
2023-02-28 11:12

Each digit in each row needs to be compared to its base value, so the running time per row is O(n). Thus, the overall time complexity is O(nlogn). If you are unlucky enough to select the minimum value as the base value each time, you will need to move the other data to the right of the base value each time and execute n rows recursively, resulting in O(n2) running time. This is the same thing as picking the minimum every time and moving it to the leftmost, which is the same thing as selecting sort. In addition, if every number in the data is equally likely to be chosen as the base value, the average running time required is O(nlogn).

yanxuefeng1516 注册会员
2023-02-28 11:12
< div class = "md_content_show e397 data - v - 3967" = "" >

so the worst-case complexity is O(n ^ 2)

About the Author

Question Info

Publish Time
2023-02-28 11:12
Update Time
2023-02-28 11:12