Skip to main content
added 290 characters in body
Source Link
Evil
  • 9.5k
  • 11
  • 32
  • 53

There is hidden linear time to perform merge part of sorting algorithm.
Linear is less than loglinear, so it was not visible. $\log1=0$, but it means that you will not e.g. heapify, just merge in $O(n)$ (heap structure in case of 1-sorted array degrades to swapping consecutive elements to perform sort).
Also all other complexities hide constant factors

Inserting element to empty heap (which might be used in such sorting) costs $O(1)$, sowhile putting element to min-heap containing $k$ elements is $O(\log k)$, which is in fact $O(\log k + c)$ drops constant part, but whenso the first looks like it becomescould be substituted with $k=1$ to have cost 0, you should reveal hidden part and say it is $O(1)$but the second reveals constant factor in asymptotic notation.

There is hidden linear time to perform merge part.
Linear is less than loglinear, so it was not visible. $\log1=0$, but it means that you will not e.g. heapify, just merge in $O(n)$.
Also all other complexities hide constant factors, so $O(\log k + c)$ drops constant part, but when it becomes 0, you should reveal hidden part and say it is $O(1)$.

There is hidden linear time to perform merge part of sorting algorithm.
Linear is less than loglinear, so it was not visible. $\log1=0$, but it means that you will not e.g. heapify, just merge in $O(n)$ (heap structure in case of 1-sorted array degrades to swapping consecutive elements to perform sort).

Inserting element to empty heap (which might be used in such sorting) costs $O(1)$, while putting element to min-heap containing $k$ elements is $O(\log k)$, which is in fact $O(\log k + c)$, so the first looks like it could be substituted with $k=1$ to have cost 0, but the second reveals constant factor in asymptotic notation.

Formatting
Source Link
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

There is hidden linear time to perform merge part.
Linear is less than loglinear, so it was not visible. $log1$ is equal 0$\log1=0$, but it means that you will not e.g. heapify, just merge in O(n)$O(n)$.
Also all other complexities hide constant factors, so $O(logk + c)$$O(\log k + c)$ drops constant part, but when it becomes 0, you should reveal hidden part and say it is $O(1)$.

There is hidden linear time to perform merge part.
Linear is less than loglinear, so it was not visible. $log1$ is equal 0, but it means that you will not e.g. heapify, just merge in O(n).
Also all other complexities hide constant factors, so $O(logk + c)$ drops constant part, but when it becomes 0, you should reveal hidden part and say it is $O(1)$.

There is hidden linear time to perform merge part.
Linear is less than loglinear, so it was not visible. $\log1=0$, but it means that you will not e.g. heapify, just merge in $O(n)$.
Also all other complexities hide constant factors, so $O(\log k + c)$ drops constant part, but when it becomes 0, you should reveal hidden part and say it is $O(1)$.

Source Link
Evil
  • 9.5k
  • 11
  • 32
  • 53

There is hidden linear time to perform merge part.
Linear is less than loglinear, so it was not visible. $log1$ is equal 0, but it means that you will not e.g. heapify, just merge in O(n).
Also all other complexities hide constant factors, so $O(logk + c)$ drops constant part, but when it becomes 0, you should reveal hidden part and say it is $O(1)$.