# What is a "negative function" withing algorithms?

I am currently studying the book 3rd edition CLRS Algorithms textbook, Chapter 3. I had the exact same question as this post but I have one more question now:

What is a negative function?

These functions are estimates that describe the time it takes to perform a function (an algorithmic sequence) onto a list. How can the function be negative if it describes the time it takes to do work? Can an algorithm sort a list 10 seconds before it starts?

• Even if your final goal is to study functions (or values) that are positive it is useful to have objects in your language that are negative. For example, you are estimating a running time, you know the total number of configurations that the algorithm must analyze and you have a branch that sometimes allows you to eliminate from the analysis certain number of cases and sometimes adds a few. What do you do? You subtract. When you try to analyze this branch by itself, you have the need for a non-positive function.
– plop
Feb 17 '21 at 21:05
• The convenience of negative numbers seems to have been known since the Han Dynasty. The fact that the final goal of the problem is to study a quantity that is a non-negative integer doesn't limit what might be useful to use in the processes of getting to that result. The same reason is why we use rational numbers, complex numbers and even zero.
– plop
Feb 17 '21 at 21:06

• Given a set of positive integers determine if it can be divided into two disjoint sets of the same size that have the same sum of its elements. The number of steps of an algorithm in terms of the number of elements of the input can easily be non-monotonic. For inputs of odd size it can return False as soon as it reads the input, while for even size it will need to do further computations.