Time Complexity of building a heap from heapify

-

We think that time complexity of buildHeap is o(nlogn) which wrong.

Time complexity of buildHeap is o(n) How ? Let us see

PROOF => 



 

Comments

Post a Comment

Popular posts from this blog

ADJACENT MATRIX

-
Image
 This usually used in representation of graphs.If there are n vertices in graph then there are  n rows and n columns in matrix. Let us take Ith row and Jth column then A[I][J] represents the edge between two nodes I  & J.If a[I][J] == 0 then there is no edge between node I and node J & if A[I][J] == 1 then there is edge. These type of graph representation is used when there are more number of edges.Reason is that if there are e less number of edges then lot of space will wasted in storing the zeroes which is not good thing. Following is the graph  and its adjancy matrix =>      # include < stdio.h > # include < stdlib.h > int main () {     // n is number of edges     int n ;     printf (" Enter the number of edges => ");     scanf (" %d ", & n );     // construct adjancy matrix     int adjMatrix [ n + 1 ][ n + 1 ];     // iterate for status of connect...
Read more

LOWEST COMMON ANCESTOR IN BST

-
 PROBLEM => FIND THE LOWEST COMMON ANCESTOR OF TWO NODES (a & b) IN BINARY                                        SEARCH TREE STEPS =>  1.Find whether these two nodes are present in bst.If not found then return NULL. 2.If both nodes are found then there are 4 possibilites =>                    1.root == a || root == b => return root                    2.a is found in left subtree and b is found in right subtree => return NULL from that subtree                                  where we cant find both a & b                    3.if a and b are found in left/right subtree return root node * lca...
Read more