0

After i have my min heap with limited size array, isn’t the complexity of insert is O(n)? In order to insert i need to increase the size of the array, but the size is limited so i need to create new array and copy the old one and after that to add the new value. So what is the complexity of insert by these terms?

1403ido
  • 1
  • 1
  • 1
    Does this answer your question? [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Welbog Jul 05 '21 at 12:13
  • 2
    [Wikipedia article on dynamic array](https://en.wikipedia.org/wiki/Dynamic_array). The basic idea is that the array is **not** reallocated at every inserted element. Occasionally, the array does need to be resized, but most of the time it does not. The worst-time time of execution *per insertion* is O(n) because of the reallocation, but the *amortized* time of execution is O(log(n)) because reallocation is rare. See also: [Wikipedia article on amortized analysis](https://en.wikipedia.org/wiki/Amortized_analysis) – Stef Jul 05 '21 at 12:37
  • Similar questions: https://stackoverflow.com/questions/29103659/amortized-analysis-on-min-heap https://stackoverflow.com/questions/55252311/amortized-analysis-on-a-binary-heap https://stackoverflow.com/questions/37798385/what-is-the-amortized-time-complexity-of-inserting-an-element-to-this-structure https://stackoverflow.com/questions/29288775/amortized-analysis-on-heap https://stackoverflow.com/questions/65187196/amortized-cost-of-insert-remove-on-min-heap https://cs.stackexchange.com/questions/59914/amortised-analysis-of-binary-heap-insert-and-delete-min – Stef Jul 05 '21 at 12:40

0 Answers0