퀵정렬 시간복잡도

[쫀꼬]

안녕하세요
이번국가직 문제도 그렇고 퀵정렬이 약점이라 공부하던중에 궁금한게 생겼습니다

보통 nlogn, 최악 n^2로 알고있습니다만 각각의 경우에 왜 시간복잡도가 저것인지 잘 모르겠습니다.. ㅎㅎ 부끄럽지만 질문드립니다

퀵정렬은 분할정복을 기반으로 한 정렬기법이며, 초기리스트 A의 길이가 n일때 피벗값 x를 기준으로 정렬한 후, 다시 피벗 x의 양옆 리스트 A1, A2도 퀵정렬해가며 초기리스트 A를 정렬하는 것으로 이해하고 있습니다

A의 길이가 n이므로 절반씩 나눠지면 0.5n, 0.25n... 은 알겠으나 외위서 아는것이지 이해해서 아는것이 아닙니다
최악의 경우는 어떤 리스트에서 피벗값을 뭘로 설정하냐에 따라 n^2가 될 수도, 아닐 수도 있는건가요?

이해하기 쉬운 예시나 문제가 있다면 알려주시길 부탁드리겠습니다
감사합니다

[홍재연]

간단하게 다음처럼 정리하면 됩니다.

1 2 3 4 5 처럼 이미 정렬된 리스트를 정렬할 때 최악이 되고 복잡도는 n^2입니다.

[홍재연]

피벗 선택 등은 무관합니다

[쫀꼬]

제가 시간복잡도 빅오표기법을 겉핥기식으로만 대충외워서 헷갈렸네요 이제 이해했습니다 감사합니다!