SELF DOUBT

Question

If you are given a sorted list with n elements in ascending order. Then what will be the Time complexity to build a Min heap from the given array?

Comments

given sorted array, apply Bubble sort ===> not O(1)

given sorted(ascending), What is time complexity to sort it ===> O(1)

Here the term, Build Min Heap, doesn't mean apply Build Heap Procedure. ( as my opinion )

---

but how machine know whether it's sorted or not ??

that's the best time complexity of bubble sort : O(n) but In our perspective it's O(1) because it's already sorted why we apply bubble sort on it  right ??

---

but how machine know whether it's sorted or not ??

Then i am questioning how BINARY SEARCH exist?

Binary Search applied on sorted input, How machine will know it is sorted?

 

i didn't say, if you apply BUBBLE SORT, it is O(1),

i said to sort it requires O(1), if you apply BUBBLE SORT, then it is O(n²) [ standard version of bubble sort ]

 

just like that

if you want to Build Min-Heap ( compare as sorting ), it is O(1), if you apply BUILD-HEAP procedure ( compare it as BUBBLE SORT ), then it is O(n).

 

In the question, the term, Build Min Heap, doesn't mean apply Build Heap Procedure. ( as my opinion )

 

BUBBLE-SORT , BUILD-HEAP ====> Procedures

Sort, Min-Heap ====> outputs

Answer 1

If its asked the minimum time, I would say time is $O(1)$ as the sorted array in ascending order satisfies the min-heap property

 

$array[i] <= array[2i]$ and $array[i] <=array[2i+1]$

If its asked time taken by build heap, it would be $O(N)$, as still the  loop runs from $floor(N/2)$ to $1$ irrespective of input:

BuildHeap(A) {
   heapsize <- length(A)
   for i <- floor( length/2 ) downto 1
      Heapify(A, i)
}