Time & Space Complexity of Heap Sort - OpenGenus IQ

The Heapsort algorithm mainly consists of two parts- converting the list into a heap and adding the max element from the heap to the end of the list, ... &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 TimeComplexity tutorial TimeandSpaceComplexityofMergeSortonLinkedList WorstCaseofMergeSort AsymptoticAnalysis TimeandSpaceComplexityofCombSort TimeandSpaceComplexityofInsertionSortonLinkedList IterationMethodforTimeComplexity RecurrenceTreeMethodforTimeComplexity SubstitutionMethodforTimeComplexity AmortizedTimeComplexity MastertheoremforTimeComplexityanalysis TimeandSpaceComplexityofCircularLinkedList TimeandSpacecomplexityofBinarySearchTree(BST) TimeandSpaceComplexityofRedBlackTree TimeandSpaceComplexityofStoogeSort TimeandSpaceComplexityofQueue 3DKadane'salgorithm StrictlyBinaryTree CompleteBinaryTree PreordertraversalinBinaryTree[Iterative+Recursive] FirstKmaximumoccurringwords BottomuptraversalofTrie Hashing:CompleteGuide MergeInsertionSort Longestwordwithgivenprefixandsuffix DataStructureusedforRecursion Algorithmtocheckwinintic-tac-toe Maximumareaofisland Generate0and1with25%and75%probability DivideandConquer BinaryHeap BubblesortvsSelectionsort DifferentPivotselectioninQuickSort DifferentHybridSortingAlgorithms CombSort HeapSort RadixSort CountingSort BucketSortAlgorithm Treesort ShellSort BinaryInsertionSort InsertionSort MergeSort QuickSort IntelligentDesignSortorQuantumBogoSort Up Getthisbook->ProblemsonArray:ForInterviewsandCompetitiveProgramming Inthisarticle,wehaveexplainedTime&SpaceComplexityofHeapSortwithdetailedanalysisofdifferentcaseslikeWorstcase,BestcaseandAverageCase. Tableofcontents: OverviewofHeapSort TimecomplexityofHeapDataStructure WorstCaseTimeComplexityofHeapSort BestCaseTimeComplexityofHeapSort AverageCaseTimeComplexityofHeapSort SpaceComplexityofHeapSort Conclusion Prerequisite:HeapSort,HeapDataStructure LetusgetstartedwithTime&SpaceComplexityofHeapSort. OverviewofHeapSort TheHeapsortalgorithmmainlyconsistsoftwoparts-convertingthelistintoaheapandaddingthemaxelementfromtheheaptotheendofthelist,whilemaintainingtheheapstructure.Foreasyimplementation,weuseamax-heapstructure,wherethemaxvaluealwaysexistsattheroot.Afterconvertingthelistintoaheap,wetakethemaxelementfromitandaddittotheendofthelist.Werepeatthisprocesstillthenumberofelementsintheheapbecomeszero.Thisindicatesthatwehavearrangedallitemsinthelistasperthecorrectorder.Sotosummarise,wefocusontwomainareaswhenimplementingheapsort- Buildingmax-heap Takingthemaximumvaluefromtheheap(therootnodevalue),addittotheendofthelist,andupdatemax-heap.Repeattillmax-heapcontainszeroitems. Thepseudocodetoimplementthisalgorithmisasfollows- lst=[a1,a2,...,aN] #heapsortthelist heapsort(lst): setheap_sizeequaltolistlength create_heap(lst) forifrom0toheap_size-1,decrementby1: lst[0],lst[i]=lst[i],lst[0] heap_size-=1 max_heapify(lst,heap_size,0) #functiontostyleaheapaspermax-heapproperties max_heapify(lst,heap_size,i): getindexofleftchildnodeofi getindexofrightchildnodeofi createavariabletotrackindexoflargestlistitem ifleftlst[largest]: largest=left ifrightlst[largest]: largest=right iflargest!=i: swap(i,largest) max_heapify(lst,heap_size,largest) #functionthatcreatesaheap #usesthemax_heapifyfunctiontocreateamax-heap create_heap(lst): getlengthoflisttogetheap_size forifromheap_size//2to-1,decrementby1: max_heapify(lst,heap_size,i) #printthesortedlistattheend heapsort(lst) print(lst) ThisgivesafundamentalideabehindtheHeapsortalgorithm. TimecomplexityofHeapDataStructure Inthealgorithm,wemakeuseofmax_heapifyandcreate_heapwhicharethefirstpartofthealgorithm.Whenusingcreate_heap,weneedtounderstandhowthemax-heapstructure,asshownbelow,works. Becausewemakeuseofabinarytree,thebottomoftheheapcontainsthemaximumnumberofnodes.Aswegoupalevel,thenumberofnodesdecreasesbyhalf.Consideringthereare'n'numberofnodes,thenthenumberofnodesstartingfromthebottom-mostlevelwouldbe- n/2 n/4(atthenextlevel) n/8 andsoon Complexityofinsertinganewnode Therefore,whenweinsertanewvalueintheheapwhenmakingtheheap,themaxnumberofstepswewouldneedtotakecomesouttobeO(log(n)).Asweusebinarytrees,weknowthatthemaxheightofsuchastructureisalwaysO(log(n)).Whenweinsertanewvalueintheheap,wewillswapitwithavaluegreaterthanit,tomaintainthemax-heapproperty.ThenumberofsuchswapswouldbeO(log(n)).Therefore,theinsertionofanewvaluewhenbuildingamax-heapwouldbeO(log(n)). Complexityofremovingthemaxvaluednodefromheap Likewise,whenweremovethemaxvaluednodefromtheheap,toaddtotheendofthelist,themaxnumberofstepsrequiredwouldalsobeO(log(n)).Sinceweswapthemaxvaluednodetillitcomesdowntothebottom-mostlevel,themaxnumberofstepswe'dneedtotakeisthesameaswheninsertinganewnode,whichisO(log(n)). Therefore,thetotaltimecomplexityofthemax_heapifyfunctionturnsouttobeO(log(n)). Complexityofcreatingaheap Thetimecomplexityofconvertingalistintoaheapusingthecreate_heapfunctionisnotO(log(n)).Thisisbecausewhenwecreateaheap,notallnodeswillmovedownO(log(n))times.It'sonlytherootnodethat'lldoso.Thenodesatthebottom-mostlevel(givenbyn/2)won'tmovedownatall.Thenodesatthesecondlastlevel(n/4)wouldmovedown1time,asthereisonlyonelevelbelowremainingtomovedown.Thenodesatthethirdlastlevelwouldmovedown2times,andsoon.Soifwemultiplythenumberofmoveswetakeforallnodes,mathematically,itwouldturnoutlikeageometricseries,asexplainedbelow- (n/2*0)+(n/4*1)+(n/8*2)+(n/16*3)+...h Herehrepresentstheheightofthemax-heapstructure. Thesummationofthisseries,uponcalculation,givesavalueofn/2intheend.Therefore,thetimecomplexityofcreate_heapturnsouttobeO(n). Totaltimecomplexity Inthefinalfunctionofheapsort,wemakeuseofcreate_heap,whichrunsoncetocreateaheapandhasaruntimeofO(n).Thenusingafor-loop,wecallthemax_heapifyforeachnode,tomaintainthemax-heappropertywheneverweremoveorinsertanodeintheheap.Sincethereare'n'numberofnodes,therefore,thetotalruntimeofthealgorithmturnsouttobeO(n(log(n)),andweusethemax-heapifyfunctionforeachnode. Mathematically,weseethat- Thefirstremoveofanodetakeslog(n)time Thesecondremovetakeslog(n-1)time Thethirdremovetakeslog(n-2)time andsoontillthelastnode,whichwilltakelog(1)time Sosummingupalltheterms,weget- log(n)+log(n-1)+log(n-2)+....log(1) aslog(x)+log(y)=log(x*y),weget =log(n∗(n−1)∗(n−2)∗…∗2∗1) =log(n!) Uponfurthersimplification(usingStirling'sapproximation),log(n!)turnsouttobe =n∗log(n)−n+O(log(n)) Takingintoaccountthehighestorderedterm,thetotalruntimeturnsouttobeO(n(log(n)). WorstCaseTimeComplexityofHeapSort Theworstcaseforheapsortmighthappenwhenallelementsinthelistaredistinct.Therefore,wewouldneedtocallmax-heapifyeverytimeweremoveanelement.Insuchacase,consideringthereare'n'numberofnodes- Thenumberofswapstoremoveeveryelementwouldbelog(n),asthatisthemaxheightoftheheap Consideringwedothisforeverynode,thetotalnumberofmoveswouldben*(log(n)). Therefore,theruntimeintheworstcasewillbeO(n(log(n)). BestCaseTimeComplexityofHeapSort Thebestcaseforheapsortwouldhappenwhenallelementsinthelisttobesortedareidentical.Insuchacase,for'n'numberofnodes- Removingeachnodefromtheheapwouldtakeonlyaconstantruntime,O(1).Therewouldbenoneedtobringanynodedownorbringmaxvaluednodeup,asallitemsareidentical. Sincewedothisforeverynode,thetotalnumberofmoveswouldben*O(1). Therefore,theruntimeinthebestcasewouldbeO(n). AverageCaseTimeComplexityofHeapSort Intermsoftotalcomplexity,wealreadyknowthatwecancreateaheapinO(n)timeanddoinsertion/removalofnodesinO(log(n))time.Intermsofaveragetime,weneedtotakeintoaccountallpossibleinputs,distinctelementsorotherwise.Ifthetotalnumberofnodesis'n',insuchacase,themax-heapifyfunctionwouldneedtoperform: log(n)/2comparisonsinthefirstiteration(sinceweonlycomparetwovaluesatatimetobuildmax-heap) log(n-1)/2intheseconditeration log(n-2)/2inthethirditeration andsoon Somathematically,thetotalsumwouldturnouttobe- (log(n))/2+(log(n-1))/2+(log(n-2))/2+(log(n-3))/2+... Uponapproximation,thefinalresultwouldbe =1/2(log(n!)) =1/2(n∗log(n)−n+O(log(n))) Consideringthehighestorderedterm,theaverageruntimeofmax-heapifywouldthenbeO(n(log(n)). Sincewecallthisfunctionforallnodesinthefinalheapsortfunction,theruntimewouldbe(n*O(n(log(n))).Calculatingtheaverage,upondividingbyn,we'dgetafinalaverageruntimeofO(n(log(n)) SpaceComplexityofHeapSort Sinceheapsortisanin-placedesignedsortingalgorithm,thespacerequirementisconstantandtherefore,O(1).Thisisbecause,incaseofanyinput- Wearrangeallthelistitemsinplaceusingaheapstructure Weputtheremoveditemattheendofthesamelistafterremovingthemaxnodefromthemax-heap. Therefore,wedon'tuseanyextraspacewhenimplementingthisalgorithm.ThisgivesthealgorithmaspacecomplexityofO(1). Conclusion Asasummary,heapsorthas: WorstcasetimecomplexityofO(n(log(n))[allelementsinthelistaredistinct] BestcasetimecomplexityofO(n)[allelementsaresame] AveragecasetimecomplexityofO(n(log(n)) SpacecomplexityofO(1) WiththisarticleatOpenGenus,youmusthavethecompleteideaofTime&SpaceComplexityofHeapSort. TimeandSpaceComplexityofMergeSortonLinkedList WorstCaseofMergeSort AsymptoticAnalysis Inthisarticle,wehaveexplainedtwoapproachestosolvetheproblemSubstringwithConcatenationofAllWords.ThisinvolvestheideaofHashMapandTwoPointer. Inthisarticle,wehaveexploredanefficientwaytoRotateImage:matrixofsizeNxNby90degrees(clockwise)inplacebyusingapropertyofXORoperation. OpenGenusIQ:ComputingExpertise&Legacy — Time&SpaceComplexityofHeapSort 🔍 Sharethis