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?

  • $\begingroup$ 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. $\endgroup$
    – plop
    Feb 17 '21 at 21:05
  • $\begingroup$ 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. $\endgroup$
    – plop
    Feb 17 '21 at 21:06

The big-O notation (and also similar notations, such as big-Omega) are not inherently limited only to describe running time of algorithms. Indeed, when the context is the running time of some algorithm, there are no negative functions since algorithms cannot run "negative time".

That being said, the big-O notation is a general mathematical definition. It could be used for other things as well, as shown in this Wikipedia page.

  • $\begingroup$ 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. $\endgroup$
    – plop
    Feb 17 '21 at 21:36
  • $\begingroup$ You are correct. I edited the answer. $\endgroup$
    – nir shahar
    Feb 17 '21 at 21:47
  • $\begingroup$ I have one more question: the book describes "asymptotically nonn-egative" and "asymptotically positive" in two different ways, implying these two terms are distinct. Are they distinct? $\endgroup$
    – linker
    Feb 18 '21 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.