Using this shortcut: The shortcut is simply find what repeats but the number of repeats should be dependent on n. Simple!
In the heap Sort, we have a for loop that repeats for n times and in each, we have the max heapify which in it, it in turn continually calls max heapify that runs down to bottom of the heap from the node in question. In worst case, this number of calls is equal to the number of subheaps from the very first root node which is simply the height of the tree. It is found that the height of a tree or heap is approximately equal to log to base 2 of n.
Thus,
Time complexity = O(nlogn)
In the heap Sort, we have a for loop that repeats for n times and in each, we have the max heapify which in it, it in turn continually calls max heapify that runs down to bottom of the heap from the node in question. In worst case, this number of calls is equal to the number of subheaps from the very first root node which is simply the height of the tree. It is found that the height of a tree or heap is approximately equal to log to base 2 of n.
Thus,
Time complexity = O(nlogn)
No comments:
Post a Comment