Each element is pushed to the heap at most twice: once for itself, once for slope adjustment after popping. Each push and pop operation is . Total operations: pushes and pops in the worst case.
Time complexity: . Space complexity: for the heap storing all breakpoints. Compare to naive DP: with means operations. Impossible. Slope Trick reduces this to , making previously impossible problems solvable in milliseconds.