Is there a useful algorithm with a decreasing asymptotic time?

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)?


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?

a Kernel free asymptotic for a sampling operator

Let $ \Pi=\left\{ t_{k}\right\} _{k\in\mathbb{Z}}$ a sequence of real numbers such that $ -\infty<t_{k}<t_{k+1}<+\infty$ for every $ k\in\mathbb{Z}$ , $ \lim_{k\rightarrow\pm\infty}t_{k}=\pm\infty$ and such that there are two positive constants $ \Delta,\,\delta $ with $ \delta\leq t_{k+1}-t_{k}\leq\Delta$ . We also define $ \Delta_{k}:=t_{k+1}-t_{k}$ , for every $ k\in\mathbb{Z}$ . We call a function $ \chi:\,\mathbb{R}\rightarrow\mathbb{R}$ a kernel if it belongs to $ L^{1}\left(\mathbb{R}\right)$ , is bounded in a neighbourhood of the origin, and satisfies the following conditions:

$ (\chi_{1})$ for every $ x\in\mathbb{R}$ $ $ \sum_{k\in\mathbb{Z}}\chi\left(u-t_{k}\right)=1;$ $

$ (\chi_{2})$ $ $ m_{1,\,\Pi}\left(\chi\right)=\sup_{u\in\mathbb{R}}\sum_{k\in\mathbb{Z}}\left|\chi\left(u-t_{k}\right)\right|\left|u-t_{k}\right|<+\infty.$ $ Let us define the following operator: $ $ \left(K_{w}^{\chi}f\right)\left(x\right):=\sum_{k\in\mathbb{Z}}\chi\left(wx-t_{k}\right)\left[\frac{w}{\Delta}_{k}\int_{t_{k}/w}^{t_{k+1}/w}f\left(u\right)du\right],\,x\in\mathbb{R}$ $ where $ f:\,\mathbb{R}\rightarrow\mathbb{R}$ is locally integrable function such that the above series is a convergent for every $ x\in\mathbb{R}$ and $ \chi$ and $ w \geq \overline{w}>0$ . Assume that exists a kernel belonging to $ C^{1}(\mathbb{R})$ such that $ \left\Vert K_{w}^{\chi}f-f\right\Vert _{\infty}=O\left(w^{-1}\right)$ as $ w \rightarrow +\infty$ , where the implicit constant depends only on $ f$ and $ \chi$ and $ \left\Vert \cdot\right\Vert _{\infty}$ is the classical sup norm.

I would like to prove that exists some $ s \neq 0$ such that $ $ \left\Vert K_{w}^{\chi_{s}}f-f\right\Vert _{\infty}=O\left(w^{-1}\right)$ $ as $ w \rightarrow +\infty$ , where $ $ \chi_{s}(\cdot)=\chi(\cdot+s)$ $ (which is obviously a kernel).

I’m quite sure that it is true but I’m not able to prove it. I tried to use $ $ \left\Vert K_{w}^{\chi_{s}}f-f\right\Vert _{\infty}\leq\left\Vert K_{w}^{\chi}f-f\right\Vert _{\infty}+\left\Vert K_{w}^{\chi_{s}}f-K_{w}^{\chi}f\right\Vert _{\infty}$ $ but it not seems very helpful. Thank you.

Asymptotic behavior of an exponential of an integral

Let $ G(x)$ be the following function $ $ G(x) = \sum_{i \in I} \alpha_i (t+x)^{\lambda_i} x^{1-\lambda_i} $ $ where we know that the coefficients sum up to one ($ \sum_{i \in I} \alpha_i = 1$ ) and that the powers appear symmetrically in the sum (i.e. $ \forall \lambda_i, i\in I$ $ \exists j \in I$ s.t. $ \lambda_j = 1-\lambda_i$ ). Then I am interested in the asymptotic behavior of $ $ \exp\left(\int^R_0 \frac{n+1}{G(x)}dx \right),$ $ where $ n$ is an integer.

More specifically, I want to show that this exponential goes asymptotically as $ R^{n+1}$ , i.e. $ $ \lim_{R \rightarrow \infty} \frac{\exp\left(\int^R_0 \frac{n+1}{G(x)}dx \right)}{R^{n+1}} = 1, $ $ or find conditions on $ \alpha_i, \lambda_i$ so that it’s true.

Asymptotic estimation of $A_n$

Let $ A_n$ represent the number of integers that can be written as the product of two element of $ [[1,n]]$ .

I am looking for an asymptotic estimation of $ A_n$ .

First, I think it’s a good start to look at the exponent $ \alpha$ such that :

$ $ A_n = o(n^\alpha)$ $

I think we have : $ 2 < alpha $ . To prove this lower bound we use the fact that the number of primer numbers $ \leq n$ is about $ \frac{n}{\log n}$ . Hence we have the trivial lower bound (assuming $ n$ is big enough) :

$ $ \frac{n}{\log n} \cdot \binom{ E(\frac{n}{\log n})}{2} = o(n^3)$ $

Now is it possible to get a good asymptotic for $ A_n$ and not just this lower bound ? Is what I’ve done so far correct ?

Thank you !

Asymptotic formula for number of square-free numbers congruent to $1$ modulo $p$

Knowing that $ \sum_{n\leq x}\mu^2(n)=\frac{6}{\pi^2}x+O(\sqrt{x})$ , prove that:

$ $ \sum_{n\leq x,\,\,n\equiv 1(\text{mod }p)}\mu^2(n)=\frac{6}{\pi^2(p-1)}x+O(\sqrt{x})$ $

Using Dirichlet charaters, we have: \begin{align*} \sum_{n\leq x,\,\,n\equiv 1(\text{mod }p)}\mu^2(n)&=\frac{1}{\varphi(p)}\sum_{n\leq x}\sum_{\chi(\text{mod }p)}\mu^2(n)\chi(n)\ &=\frac{1}{\varphi(p)}\sum_{\chi(\text{mod }p)}\sum_{n\leq x}\mu^2(n)\chi(n)\ &=\frac{1}{\varphi(p)}\sum_{n\leq x}\mu^2(n)\chi_0(n)+\underbrace{\frac{1}{\varphi(p)}\sum_{\chi\neq \chi_0}\sum_{n\leq x}\mu^2(n)\chi(n)}_{=:\Delta(x)} \end{align*} Where $ \chi_0$ is the principal character. I was able to prove that $ \Delta(x)=O(\sqrt{x})$ basically by using the fact that $ \mu^2(n)=\sum_{d|n}\mu(d)$ , and that $ \left|\sum_{n\leq x}\chi(n)\right|\leq \varphi(p)$ . My problem is the main term, which doesn’t match my calculation.

By definition, $ \chi_0(n)=1$ if $ p\not| n$ and $ \chi_0(n)=0$ if $ p|n$ . Therefore: \begin{align*} \frac{1}{\varphi(p)}\sum_{n\leq x}\mu^2(n)\chi_0(n)&=\frac{1}{\varphi(p)}\sum_{n\leq x}\mu^2(n)-\frac{1}{\varphi(p)}\sum_{n\leq x,\,\,p|n}\mu^2(n)\ &=\frac{1}{\varphi(p)}\sum_{n\leq x}\mu^2(n)-\frac{1}{\varphi(p)}\sum_{n\leq \frac{x}{p}}\mu^2(n)\ &=\frac{1}{\varphi(p)}\left(\frac{6}{\pi^2}x-\frac{6}{\pi^2}\frac{x}{p}\right)+O(\sqrt{x})\ &=\frac{6x}{\pi^2\varphi(p)}\left(1-\frac{1}{p}\right)+O(\sqrt{x})\ &=\frac{6}{\pi^2p}x+O(\sqrt{x}) \end{align*} What am I missing?