COURSES
MBAData Science & AnalyticsDoctorate Software & Tech AI | ML MarketingManagement
Professional Certificate Programme in HR Management and AnalyticsPost Graduate Certificate in Product ManagementExecutive Post Graduate Program in Healthcare ManagementExecutive PG Programme in Human Resource ManagementMBA in International Finance (integrated with ACCA, UK)Global Master Certificate in Integrated Supply Chain ManagementAdvanced General Management ProgramManagement EssentialsLeadership and Management in New Age BusinessProduct Management Online Certificate ProgramStrategic Human Resources Leadership Cornell Certificate ProgramHuman Resources Management Certificate Program for Indian ExecutivesGlobal Professional Certificate in Effective Leadership and ManagementCSM® Certification TrainingCSPO® Certification TrainingLeading SAFe® 5.1 Training (SAFe® Agilist Certification)SAFe® 5.1 POPM CertificationSAFe® 5.1 Scrum Master Certification (SSM)Implementing SAFe® 5.1 with SPC CertificationSAFe® 5 Release Train Engineer (RTE) CertificationPMP® Certification TrainingPRINCE2® Foundation and Practitioner Certification
Law
Job Linked
Bootcamps
Study Abroad
Master of Business Administration (90 ECTS)Master of Business Administration (60 ECTS)Master in Computer Science (120 ECTS)Master in International Management (120 ECTS)Bachelor of Business Administration (180 ECTS)B.Sc. Computer Science (180 ECTS)MS in Data AnalyticsMS in Project ManagementMS in Information TechnologyMasters Degree in Data Analytics and VisualizationMasters Degree in Artificial IntelligenceMBS in Entrepreneurship and MarketingMSc in Data AnalyticsMS in Data AnalyticsMaster of Science in AccountancyMS in Computer ScienceMaster of Science in Business AnalyticsMaster of Business Administration MS in Data ScienceMS in Information TechnologyMaster of Business AdministrationMS in Applied Data ScienceMaster of Business AdministrationMS in Data AnalyticsM.Sc. Data Science (60 ECTS)Master of Business AdministrationMS in Information Technology and Administrative Management MS in Computer Science Master of Business Administration MBA General Management-90 ECTSMSc International Business ManagementMS Data Science MBA Business Technologies MBA Leading Business Transformation Master of Business Administration MSc Business Intelligence and Data ScienceMS Data Analytics MS in Management Information SystemsMSc International Business and ManagementMS Engineering ManagementMS in Machine Learning EngineeringMS in Engineering ManagementMSc Data EngineeringMSc Artificial Intelligence EngineeringMPS in InformaticsMPS in Applied Machine IntelligenceMS in Project ManagementMPS in AnalyticsMS in Project ManagementMS in Organizational LeadershipMPS in Analytics - NEU CanadaMBA with specializationMPS in Informatics - NEU Canada Master in Business AdministrationMS in Digital Marketing and MediaMS in Project ManagementMaster in Logistics and Supply Chain ManagementMSc Sustainable Tourism and Event ManagementMSc in Circular Economy and Sustainable InnovationMSc in Impact Finance and Fintech ManagementMS Computer ScienceMS in Applied StatisticsMS in Computer Information SystemsMBA in Technology, Innovation and EntrepreneurshipMSc Data Science with Work PlacementMSc Global Business Management with Work Placement MBA with Work PlacementMS in Robotics and Autonomous SystemsMS in Civil EngineeringMS in Internet of ThingsMSc International Logistics and Supply Chain ManagementMBA- Business InformaticsMSc International ManagementMS Computer Science with AIML ConcentrationMBA in Strategic Data Driven ManagementMaster of Business AdministrationMSc Digital MarketingMBA Business and MarketingMaster of Business AdministrationMSc Digital MarketingMSc in Sustainable Luxury and Creative IndustriesMSc in Sustainable Global Supply Chain ManagementMSc in International Corporate FinanceMSc Digital Business Analytics MSc in International HospitalityMSc Luxury and Innovation ManagementMaster of Business Administration-International Business ManagementMS in Computer EngineeringMS in Industrial and Systems EngineeringMSc International Business ManagementMaster in ManagementMSc MarketingMSc Business ManagementMSc Global Supply Chain ManagementMS in Information Systems and Technology with Business Intelligence and Analytics ConcentrationMSc Corporate FinanceMSc Data Analytics for BusinessMaster of Business AdministrationMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSBachelors in International Management
For College Students

Quick Sort Time Analysis in Data Structure

$$/$$

Now that you have seen the pseudocode for QuickSort and also seen its Java implementation, it is now time to know about the time complexity of the QuickSort algorithm. Let us find out in the coming video how Quicksort fares out when it comes to time complexity.

 

In the first video, you are going to take a look at the partition function and how much time does it take for that function to execute. Then in the next videos, you are going to see what is the time complexity in the best and the worst case of the QuickSort algorithm.

$$/$$

Video Transcript

 

Now let us take a look at the time complexity of the Quicksought algorithm. So here my Quicksort uses a partition function. So let us first see what is the time complexity of our partition function. So here in my partition function, in the first two steps I am just calculating and assigning values to the variables pivot and p. There is no extra computation involved and I am just assigning some particular values to these variables. So these two steps are going to take a constant amount of time. Moreover, if you notice here in the last two steps also I am just exchanging the values of A of p and A of end, which is independent of the size of my input array. Moreover, in the last step when I'm returning p, this also does not involve any dependency on the number of elements in the array. So both these operations are also running in constant amount of time. Now, let us look at this for loop. Now, here the inside operations which are happening in this if loop, they are also of constant time since

 

we are only swapping these two elements and changing the value of p. So this particular steps take a constant amount of time. But if you notice here carefully, this is enclosed inside a for loop and this for loop runs its iterator I from start till the end, which means that I is dependent on N. That is, if I have eight elements, this for loop is going to run eight times. And if I have 1 million elements, this for loop is going to run 1 million times. So this means that this for loop is dependent on N. So this gives me that this entire procedure is of the order of N. That is for running this for loop it would require order N amount of time. So now, all of these operations which are occurring in a constant amount of time are independent of the number of elements in our array. That is, it does not really matter if my array has eight elements or 1 million elements, because this Pivot and p assignment steps are going to take a constant amount of time and same is the case with these two steps.

 

However, this for loop clearly depends on N. So what is the total time complexity of this partition operation? Well, the total time complexity of this partition operation will be C plus N plus C. That is this partition operation is going to take C for these two steps and N times for when the for loop is going to run and C for these two operations. So this gives me N plus some constant C prime. So basically in the conclusion, you should remember that this entire partition function occurs in order N amount of time.

 

Video Recap

 

  • Quicksort algorithm uses a partition function

  • Partition function time complexity analysis

  • First two steps in partition function assign values to pivot and p, no extra computation involved

  • Last two steps involve exchanging values of A of p and A of end, which is independent of input array size

  • Returning p also does not involve any dependency on the number of elements in the array

  • Inside operations in the for loop are also of constant time since only swapping two elements and changing value of p

  • For loop runs from start till end and is dependent on N

  • Entire procedure is of order N, dependent on N

  • Partition operation time complexity is C + N + C

  • Partition operation occurs in order N amount of time

  • Total time complexity of partition operation is N + some constant C prime

 

 

Now that you have seen the time complexity of the Partition function of Quicksort, we will now learn about how much time does it take for the actual Quick Sort algorithm to run. In the next video, you are going to see the time complexity of Quick Sort in the worst case. 

$$/$$

Till now you have seen the worst case time complexity of the Quick Sort algorithm. In the coming video, we will see what is the time complexity of Quick Sort in the best case.

$$/$$

Great! Now we have successfully derived the time complexity expressions of the best and the worst case of the Quick Sort algorithm. Aishwarya will now summarise the time complexities of the Quick Sort in the coming video, comparing the best, worst and average case time complexities of Quick Sort.

$$/$$

Quicksort also comes out to have a time complexity of O(N log N). However, in the worst case, its time complexity is O(N). Despite this, most of the cases we encounter are closer to the average case and not the worst or best cases. So, again it is one of the most widely used algorithms because of its time complexity.

Here is the link for time complexity analysis of Quicksort in detail. 

Please refer to the link below on how to chose a random pivot. 

 

That was interesting, wasn’t it? In the next section, you are going to see through a game of cards how Quick Sort works.