00:00Now let's discuss a special thing for our quicksort. When is the worst case time complexity?
00:06We will see this lecture when we have time complexity clear, space complexity etc.
00:14We can skip this lecture, we can also see this chapter after the time complexity.
00:18In the first case time complexity, when my array is sorted in ascending order or descending order.
00:25And this will come when my pivot element is always smallest or largest element.
00:30How? Let's assume that my array is like this.
00:331, 2, 3, 4, 5.
00:36What will happen if I always take my last element?
00:40What can I say? If my pivot element is always last element, then my pivot element will always be the
00:45largest element of the array.
00:47Why?
00:48Because in ascending order, the last element is always the largest of the array.
00:53If I call the quicksort here, then it will divide the partition in 2 parts.
00:58If there is a partition in 5, then what will happen before this?
01:01I will have 1, 2, 3 and then 4.
01:04And in the last, I will have left.
01:05I will choose pivot from 4.
01:07If 4 will choose, then it will divide in 2 parts.
01:09Then it will divide between 4.
01:11And here I will have 1, 2 and 3.
01:14I will leave left.
01:15Now I will choose 3 as pivot.
01:17If 3 as pivot choose, then 3 will come in middle.
01:20It will divide in 2 parts.
01:21In the first part, I will have 1 and 2.
01:24And the other part will be left.
01:26I will choose 2.
01:26After that, I will choose 2 again.
01:28I will choose 2 around.
01:29I will have sorting.
01:30So this will come in middle.
01:32And here I will have 1.
01:34So what happens every time?
01:35Every time my pivot is the last element.
01:38That is the largest element.
01:39So every time my array size.
01:41I can say that if I understand recursion.
01:45So what is my array size in the first level?
01:48How many times I have to reverse?
01:49How many times I have to go into partition?
01:52Or I am talking about partition function.
01:54In partition function, my loop will go into n times.
01:59In this level, my time complexity will be n-1.
02:04In this level, my time complexity will be n-2.
02:07In this level, my time complexity will be n-2.
02:08In this level, n-3.
02:09In this level, n-4.
02:11And in this way, it will go into 1.
02:14In this level, my time complexity will be n-1.
02:17In this level, my time complexity will be n-1.
02:17Then, n-1.
02:18Then, n-2.
02:19Then, n-2.
02:20Then, n-3.
02:20And I will add total time complexity.
02:23So I will add them all.
02:25So n plus n-1.
02:27Plus n-2.
02:28Plus n-3.
02:30In this way, I will add them all.
02:34So what can I say?
02:35Here I have arithmetic progression.
02:37I can say 1 plus 2 plus 3 plus 4.
02:40And where are we going?
02:41To n.
02:42So what is the sum?
02:43The sum is n into n plus 1 by 2.
02:46What is n-2 plus n by 2?
02:50And I can say that this will be big of n-2.
02:55So when will it be worst case?
02:56The worst case is when my ascending order is always the largest element.
03:01In this case, every single level will increase time complexity.
03:05So the final worst case time complexity will be n-2.
03:08And if this is the same case, if it is sorted in descending order,
03:10If this area is sorted,
03:11If this area is over,
03:13Then the pivot is always the smallest element.
03:15So this case is the same n-2 time complexity.
03:18Now the question is,
03:19If this is the worst case time complexity,
03:29This is the worst case time complexity,
03:31It's the worst case time complexity,
03:32When my pivot element,
03:33area is always the smallest element.
03:37It is always the smallest element.
03:39Or the largest element.
03:39So this is the smallest element of time.
03:40If this area is the smallest element,
