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 Bubble Sort in Data Structures

$$/$$

Video Transcript

 

So now we are going to analyze what is the time complexity of bubble sort. So here as you saw that this was my worst case scenario when I required the maximum number of comparisons since all my elements were out of order. Now if you look carefully, in my first iteration I did four number of comparisons. So since had five elements here, in the first step I did four comparisons. So this implies that in the first step I did a total of n minus one comparisons. Now similarly in the second iteration I performed three comparisons. So that means I did five minus two number of comparisons, that would be n minus two. Similarly for the third iteration I did n minus three comparisons here, n minus four comparisons and so on till my last step when I did exactly one comparison to see whether all my elements are in order. So now what is the total time required for this the total number of comparisons? My total number of comparisons can be written by this expression t n is equal to one plus two plus three, 

 

so on plus n minus two till n minus one. So t n can be written as one plus two till n minus one. Now, if you look at this expression carefully you would see that this is nothing but the sum of all the natural numbers starting from one till n minus one. You know that for natural numbers the sum of the first natural numbers can be written as n into n plus one by two. Here my capital n will be replaced by n minus one. Since I need to find the sum of first n minus one natural numbers, this can be then written as n minus one into n minus one plus one which gives me n divided by two. On solving this expression I would get half of n square minus n. Now if you look at this expression carefully you would see that here in comparison to n square n will always be a smaller number. So I can conveniently ignore this. Moreover, this half outside of this bracket is a constant which can also be ignored. So this gives me an expression that t n is of the order n square. So basically the time complexity of bubble sort will then become theta of n square. So finally we conclude that it requires order n square number of comparisons for bubble sort to perform. 

 

Video Recap

 

  • Bubble sort's time complexity is being analyzed

  • Worst case scenario is when all elements are out of order

  • The total number of comparisons can be written as

  • This expression is the sum of all natural numbers from to

  • The sum of the first n natural numbers can be written as

  • Therefore, tn can be written as

  • This simplifies to , which is of the order

  • Hence, the time complexity of bubble sort is theta of

  • Bubble sort requires order number of comparisons to perform

 

Great! So, as discussed, bubble sort has a time complexity of (), where N is the number of elements in the array. In first iteration, it does comparisons ; in the second iteration it does comparisons; in third, it does comparisons. This continues for a total of iterations. So, the total number of comparisons effectively become the sum of first natural numbers. 

In the next video, you will see sorting of a deck of six cards using the algorithm you just learnt about. Let’s see how it’s done.

$$/$$

The video reinforces your takeaways from this lesson on bubble sort. The time complexity calculated from the actual number of steps required comes out to be the same as that discussed by Aishwarya. In the next segment, you will move to the next sorting algorithm — Selection sort.