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 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 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 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 at 22:13
3
$\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 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 at 22:07
  • $\begingroup$ @Makogan $O(1)$ is already as tight as possible for any algorithm. $\endgroup$ – Dmitri Urbanowicz Jan 5 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 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 at 8:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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