Time and Space complexity of Bubble Sort - OpenGenus IQ

Θ(N^2) is the Average Case Time Complexity of Bubble Sort. The number of comparisons is constant in Bubble Sort so in average case, there is O(N^2) comparisons. &times Home Discussions WriteatOpengenusIQ &times × Searchanything: Interestingposts TopCompetitiveProgrammers UnsolvedProblemsinAlgorithms ToppatentholdersinIndia HowtogetDeveloperJobinJapan? [INTERNSHIP] STORY:MostProfitableSoftwarePatents HowtoearnbyfilingPatents? RichestProgrammersintheWorld STORY:Multiplicationfrom1950to2022 PositionofIndiaatICPCWorldFinals(1999to2021) MostDangerousLineofCode💀 AgeofAllProgrammingLanguages HowtoearnmoneyonlineasaProgrammer? STORY:KolmogorovN^2ConjectureDisproved STORY:manwhorefused$1Mforhisdiscovery STORY:ManbehindVIM STORY:Galacticalgorithm STORY:InventorofLinkedList PracticeInterviewQuestions Listof50+BinaryTreeProblems Listof100+DynamicProgrammingProblems Listof50+ArrayProblems 11GreedyAlgorithmProblems[MUST] Listof50+LinkedListProblems 100+GraphAlgorithmsandTechniques Algorithms tutorial 3DKadane'salgorithm StrictlyBinaryTree CompleteBinaryTree PreordertraversalinBinaryTree[Iterative+Recursive] FirstKmaximumoccurringwords BottomuptraversalofTrie Hashing:CompleteGuide MergeInsertionSort Longestwordwithgivenprefixandsuffix DataStructureusedforRecursion Algorithmtocheckwinintic-tac-toe Maximumareaofisland Generate0and1with25%and75%probability DivideandConquer BinaryHeap TimeandSpaceComplexityofMergeSortonLinkedList WorstCaseofMergeSort AsymptoticAnalysis TimeandSpaceComplexityofCombSort TimeandSpaceComplexityofInsertionSortonLinkedList IterationMethodforTimeComplexity RecurrenceTreeMethodforTimeComplexity SubstitutionMethodforTimeComplexity AmortizedTimeComplexity MastertheoremforTimeComplexityanalysis TimeandSpaceComplexityofCircularLinkedList TimeandSpacecomplexityofBinarySearchTree(BST) TimeandSpaceComplexityofRedBlackTree TimeandSpaceComplexityofStoogeSort TimeandSpaceComplexityofQueue BubblesortvsSelectionsort DifferentPivotselectioninQuickSort DifferentHybridSortingAlgorithms CombSort HeapSort RadixSort CountingSort BucketSortAlgorithm Treesort ShellSort BinaryInsertionSort InsertionSort MergeSort QuickSort IntelligentDesignSortorQuantumBogoSort Up Getthisbook->ProblemsonArray:ForInterviewsandCompetitiveProgramming InthisarticlewewillexplorethetimeandspacecomplexityofapopularsortingalgorithmcalledBubbleSort.Wewillalsoexploreanoptimizationofthisalgorithmandit'scomplexity. TableofContents: IntroductiontoBubblesort TimeComplexityAnalysis WorstCaseTimeComplexity BestCaseTimeComplexity AverageCaseTimeComplexity SpaceComplexity ComparisonwithotherSortingAlgorithms IntroductiontoBubblesort Bubblesortisanalgorithmthatsequentiallystepsthroughalistofitemsandswapsitemsiftheyaren'tinthecorrectordertillthelistissorted. Here'sanexampleofthesortingtechniquevisualized: Asthevisualshows,theelementsseemtobubbleuptotheircorrectpositionsinthelistandthusthenameofbubblesort.Itisalsoreferredtoascomparisonorsinkingsort. Pseudocode 1.procedurebubbleSort(A:listofsortableitems) 2.n:=length(A) 3.fori:=0ton-1inclusivedo 4.forj:=0ton-i-1inclusivedo 5.//theelementsaren'tintherightorder 6.ifA[j]>A[j+1]then 7.//swaptheelements 8.swap(A[j],A[j+1]) 9.endif 10.endfor 11.endfor 12.endprocedure TimeComplexityAnalysis InthisunoptimisedversiontheruntimecomplexityisΘ(N^2).Thisappliestoallthecasesincludingtheworst,bestandaveragecasesbecauseevenifthearrayisalreadysortedthealgorithmdoesn'tcheckthatatanypointandrunsthroughalliterations.Althoughthenumberofswapswoulddifferineachcase. Thenumberoftimestheinnerloopruns $=\sum_{j=1}^{N-i-1}1\tag{2}$ $=(N-i)\tag{1}$ Thenumberoftimestheouterloopruns $=\sum_{i=1}^{N-1}\sum_{j=1}^{N-i-1}1=\sum_{i=1}^{N-1}N-i\tag{3}$ $=\frac{N*(N-1)}{2}\tag{4}$ Optimization Weaddanadditionalcheckthatbreaksoutoftheouterloopifnoswapsoccurintheinnerloop. Implementation 1.voidbubbleSort(vector&v){ 2.intn=v.size(); 3.boolswapped=true; 4.inti,j; 5.for(i=0;iv[j+1]){ 9.//elementsareoutoforder 10.swap(v[j],v[j+1]); 11.//rememberaswapoccurred 12.swapped=true; 13.} 14.} 15.//checkifarrayissorted 16.if(swapped==false)break; 17.} 18.} Complexity Nowwecananalyzethe: TimecomplexityT(N) NumberofswapsS(N) NumberofcomparisonsC(N) foreachcase.Thisisdonebyobservingthenumberoftimesthelines8-13runineachcase. T(N)=S(N)+C(N) TimeComplexity=NumberofSwaps+NumberofComparisons Therelationareasfollows: T(N)=T(N-1)+N C(N)=C(N-1)+(N-1) S(N)dependsonthedistributionofelements. WorstCaseTimeComplexity Θ(N^2)istheWorstCaseTimeComplexityofBubbleSort. Thisisthecasewhenthearrayisreverselysorti.e.indescendingorderbutwerequireascendingorderorascendingorderwhendescendingorderisneeded. Thenumberofswapsoftwoelementsisequaltothenumberofcomparisonsinthiscaseaseveryelementisoutofplace. $T(N)=C(N)=S(N)=\frac{N*(N-1)}{2}$,fromequation2and4 Therefore,intheworstcase: NumberofComparisons:O(N^2)time Numberofswaps:O(N^2)time BestCaseTimeComplexity Θ(N)istheBestCaseTimeComplexityofBubbleSort. Thiscaseoccurswhenthegivenarrayisalreadysorted. Forthealgorithmtorealisethis,onlyonewalkthroughofthearrayisrequiredduringwhichnoswapsoccur(lines9-13)andtheswappedvariable(false)indicatesthatthearrayisalreadysorted. $T(N)=C(N)=N$ $S(N)=0$ Therefore,inthebestcase: NumberofComparisons:N=O(N)time Numberofswaps:0=O(1)time AverageCaseTimeComplexity Θ(N^2)istheAverageCaseTimeComplexityofBubbleSort. ThenumberofcomparisonsisconstantinBubbleSortsoinaveragecase,thereisO(N^2)comparisons.Thisisbecauseirrespectiveofthearrangementofelements,thenumberofcomparisonsC(N)issame. Forthenumberofswaps,considerthefollowingpoints: IfanelementisinindexI1butitshouldbeinindexI2,thenitwilltakeaminimumofI2-I1swapstobringtheelementtothecorrectposition. AnelementEwillbeatadistanceofI3fromitspositioninsortedarray.MaximumvalueofI3willbeN-1fortheedgeelementsanditwillbeN/2fortheelementsatthemiddle. Thesumofmaximumdifferenceinpositionacrossallelementswillbe: (N-1)+(N-3)+(N-5)...+0+...+(N-3)+(N-1) =NxN-2x(1+3+5+...+N/2) =N^2-2xN^2/4 =N^2-N^2/2 =N^2/2 Therefore,inaverage,thenumberofswaps=O(N^2). Therefore,intheaveragecasetimecomplexityofBubblesort: NumberofComparisons:O(N^2)time Numberofswaps:O(N^2)time SpaceComplexity Thealgorithmonlyrequiresauxiliaryvariablesforflags,temporaryvariablesandthusthespacecomplexityisO(1). ComparisonwithotherSortingAlgorithms Thebubblesortalgorithmismainlyusedtoexplaintheoreticalaspectsincludingcomplexityandalgorithmdesignbutrarelyusedinpracticebecauseofhowitscaleswithlargeramountsofdata.Somecomplexitiesofotherpreferredsortingalgorithmsare: Algorithm BestCase AverageCase WorstCase BubbleSort Ω(n) Ω(n^2) Ω(n^2) SelectionSort Ω(n^2) θ(n^2) O(n^2) InsertionSort Ω(n) θ(n^2) O(n^2) HeapSort Ω(nlog(n)) θ(nlog(n)) O(nlog(n)) QuickSort Ω(nlog(n)) θ(nlog(n)) O(n^2) MergeSort Ω(nlog(n)) θ(nlog(n)) O(nlog(n)) BucketSort Ω(n+k) θ(n+k) O(n^2) Note:BubbleSortandInsertionSortisefficientforthebestcasethatiswhenthearrayisalreadysorted. WiththisarticleatOpenGenus,youmusthavethecompleteideaofTimeandSpaceComplexityofBubbleSort. BubblesortvsSelectionsort 3DKadane'salgorithm Backjumping Inthisarticle,wehavecoveredhowtopassavectortoafunctionasfunctionargumentinC++withvariantslike1Dvector,2Dvector,3Dvector,globalvectorandglobalvectorbyvalue.Wehavealso,coveredhowtoreturnavectorfromafunction. Inthisarticle,wehaveexplainedhowtoinsertanelementatthebottomofStackusingstandardstackoperationslikepushandpop.Wehavecoveredtwoapproaches:iterativeandrecursive. OpenGenusIQ:ComputingExpertise&Legacy — TimeandSpacecomplexityofBubbleSort 🔍 Sharethis