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

Analysis of Insertion Sort in Data Structures

$$/$$

In this video, we will analyse insertion sort algorithm. Let’s get started.

$$/$$

Video Transcript

 

So now we'll take a look at the time complexity of the insertion sort algorithm. For that, let us take an array like this. Now you would see that I would again begin from this point and compare four with five. I would find that I am doing one comparison here and swapping. So if I say that TN is my number of comparisons, I am doing exactly one comparison here when I'm comparing four with five. So let me write one here and I would swap them. So in my next iteration my array will look something like this.

 

Now I would begin at this point and compare three with five. So I will swap them since three is less than five and I would once again compare three with four, I would see that three is less than four so I would again swap them. So how many times did I compare three with these? I compared two times. So let me write two here. Now in the next iteration my array looks like this.

 

I start from this point and compare all the elements which are to the left of two. I would see that five is exchanged with two. Similarly, since two is less than four I'll swap them and since two is also less than three, I'll swap them again. So what is the total number of comparisons I'm doing? Two is getting compared to five, then four, then three. So I'm doing a total number of three comparisons. Now my array looks like this.

 

When I move to the last of my elements I would be again needing to compare it with all the elements to its left. So one would get compared to five and since one is less than five we would swap them. So this is one comparison. Now one will get compared to four and since one is less than four I would swap them. So that was my second comparison. Now my one will get compared to three and since one is less than three, again I will swap them. This was my third comparison and lastly my one will get compared to two and since one is less than two I'll swap them again. This was my fourth comparison. So in this particular iteration I did a total of four comparisons. So now if you observe carefully for any given array of length n here my n is equal to five. Since there are five elements in my array, my first iteration will have one comparison, my second iteration will have two number of comparisons, my third will have three and fourth will have four. So now for an array of length n, these number of

 

comparisons can be generalized and written in terms of n. Like this here I have four. So this basically reduces to n minus one because my n was five here, this three can be written as n minus two. Similarly I'll go on from n minus one, n minus two, n minus three and my number of comparisons will keep on decreasing till I reach a point where I'm doing two and one number of comparisons. Now let me just find the summation of all these total number of comparisons to calculate my time complexity. So here t of n will be written as one plus two plus three till n minus one. So you have seen this expression before. This is nothing but the sum of all natural numbers starting from one and going till n minus one. So you have already seen that this summation is equal to n minus one into n divided by two. This can be alternatively written as half of N square minus N. Now again, looking at this expression, you would see that I can ignore the half here since it is a constant. And I can also ignore the

 

N here since N square will always be greater than N. So basically my T of N gets reduced to theta of N square. So in conclusion, we can say that the time complexity of insertion sort is of the order of n square.

 

Video Recap

 

  • time complexity of the insertion sort algorithm

  • The speaker uses an example array of 5 elements to illustrate the number of comparisons needed in each iteration of the algorithm

  • The total number of comparisons for an array of length n can be generalized and written as and so on until 1

  • The time complexity of the algorithm can be calculated by finding the summation of all these comparisons

  • The final time complexity of insertion sort is of the order of n square

 

Erratum: At timestamp 04:58, the tome complexity should be O and not theta

 

So, insertion sort again comes out to have a time complexity of O(N). However, it follows O(N) in the best case. So, if the array is almost sorted, i.e. it is nearer to the best case than the worst case, the insertion sort will have a time complexity somewhere between O(N) and O(N). It will be nearer to O(N) if the array is almost sorted, and nearer to O(N) if the array is arranged in the opposite order of our preference. For example, consider an array where all elements are in descending order, and you want to sort it in ascending order. In such a case, it will be closer to O(N). Watch the video below to understand this better.

$$/$$

That was interesting, wasn’t it? It’s always a good practice to verify what you learn with something in real time Here as well insertion sort comes out to have  time complexity of O(N) in the worst case, and O(N) in the best case. Remember that you only need to do comparisons; no swaps are done when the cards are already in ascending order.