0
$\begingroup$

Algorithmic complexity is usually increasing and almost always strictly increasing based on input size. This is logical since algorithms take time to execute steps, and for almost all problems, the larger the input the more steps are needed to handle that input.

I want to know if there is an algorithm that does not increase with input size but rather decreases.

You could make an algorithm with decreasing asymptotic time by for example, making it loop -n + 10000 times, where n is the size of an array of integers.

This however doesn't do anything other than cycling, it shows that you could make such an algorithm, if the algorithm doesn't do anything useful. Is there an algorithm that decreases asymptotically as the size of the input increases, that solves an actual problem (theoretical or other)?

EDIT:

Some people seem to be getting confused by the question so i want to clarify.

Is there a non-trivial algorithm that executes less steps as the size of the input increases?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I literally just want to know if there is an algorithm that runs less as the size of it;s input increases $\endgroup$ – Makogan Jan 4 '19 at 21:07
  • $\begingroup$ Using the term "complexity" muddies the waters here, but note that runtime cost almost never "strictly increases based on input size". $\endgroup$ – Raphael♦ Jan 4 '19 at 22:05
  • $\begingroup$ @Raphael Sorting and searching, the basis of most algorithms, are strictly increasing functions based on input size, it's the case for djikstra, merge sort, matrix multiplication, looking for an entry in a binary tree... $\endgroup$ – Makogan Jan 4 '19 at 22:07
  • $\begingroup$ Nope. The rough $O$-bounds you see are strictly increasing, but that's hardly the full truth. For example, the (worst-/average-/best-case) number of comparisons in binary search is increasing, but not strictly increasing. $\endgroup$ – Raphael♦ Jan 4 '19 at 22:13
4
$\begingroup$

No. If the running time is approaching zero as the input size grows, then the algorithm can’t even perform a single step.

If you mean that the running time approaches some positive constant, then this is just $O(1)$, because $\Omega(1)$ is a lower bound for any algorithm.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Saying O(1) upper bounds any decreasing function asymptotically is not much more helpful than saying that all increasing functions are in $\Omega(1)$, it's technically correct but provides little insight as there are tighter bounding functions $\endgroup$ – Makogan Jan 4 '19 at 22:04
  • $\begingroup$ The question is not super clear regarding what's wanted, but note that $2 + \frac{1}{\log n}$ is strictly decreasing and in $\Theta(1)$. It's true that no algorithm can have running time in $o(1)$. $\endgroup$ – Raphael♦ Jan 4 '19 at 22:07
  • $\begingroup$ @Makogan $O(1)$ is already as tight as possible for any algorithm. $\endgroup$ – Dmitri Urbanowicz Jan 5 '19 at 9:56
  • $\begingroup$ @DmitriUrbanowicz For an asymptotically increasing function yes, however $O(1)$ is a worse asymptotic bound for $f(n) = -n$ than $f(-n)$, trivially. $\endgroup$ – Makogan Jan 5 '19 at 16:31
  • $\begingroup$ @Makogan you can’t run an algorithm for zero, 0.34 or negative number of steps. It has to be at least one, thus $\Omega(1)$ lower bound. Increasing functions are irrelevant here. $\endgroup$ – Dmitri Urbanowicz Jan 6 '19 at 8:11
0
$\begingroup$

I think everyone knows useful algorithms with constant complexity, e.g. test if a number is even by checking the last bit, or negative by checking the sign bit. You might need to argue for a random access model to the input if you can't guarantee you see the start or end of the stream first (big/little endian issues) but still one of these is valid and used all the time. That is not strictly decreasing but it does, as asked, solve a useful problem with a subset of the input.

But there are many reasonable algorithms with such features. Take a Monte Carlo algorithm that learns how much white space is in a document. It can sample less and less of a larger document and still have reasonable statistics. Polling data is this way too.

Also consider machine learning. When I worked on natural language recognition years back we found you don't keep training on equal proprotions of data, you can reduce the amount you sample as you get a larger corpus to study. I'd call that a form of "decreasing".

I think the main issue is as Raphael mentioned the word "complexity" which invites a purely asymptotic tone. If so you ignore any changes in behavior before some constant size $B$. And so to be a decreasing function from that point on would be hard to do meaningfully. But what about a function like $O(n^{1/n})$, doesn't that have some meaningfully "decreasing" complexity without being a strictly decreasing function?

I would argue that decreasing has a natural interpretation that is meaningful, e.g. that an algoirthm in some initial range behaves quadratically, but in large enough inputs can become linear.

A real life example of what I mean is matrix multiplication. The complexity by Coppersmith-Winograd is around $O(n^{2.3})$ but it takes a very large $n$ to get to that complexity. So in reality we model it something like $O(n^3)$ for $n<100$, swapping to $O(n^{2.7})$ for some regime $100\leq n\leq 1,000,000$, and perhaps some other complexities after that all the way until we hit the extreme regime. (Yes experts, those ranges are hypothetical for illustration, not the result of citing some specific test suit!)

That I would argue is a form of "decreasing" complexity and found quite often in useful algorithms.

|cite|improve this answer
$\endgroup$

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.