CODEWITHSUNDEEP
performancealgorithmcomplexity-theorybig-o
ocwirk
ocwirk

Reputation: 1089

Is it possible that time complexity of any algorithm decrease as the input size increase, any example

I just read in Cormen's algorithm book that big-O and big-omega do not follow the trichotomy property. That means for two functions, f(n) and g(n), it may be the case that neither f(n) = O(g(n)) nor f(n) = Omega(g(n)) holds. In example they argue that if function is n^(1+sin n) than it is possible.

While it is correct is it possible in a real world algorithm to have a run time of something like sin n. Since it would sometimes decrease, with the increase of input size. Does anybody knows any such algorithm or can give a small code snippet which does this.

Thanks for the answers, so in that case is it correct to assume that Given a problem P with size n, if it can not be solved in O(f(n)) time by any known algorithm, then the lower bound of P is Omega(f(n)).

Upvotes: 18

Views: 4931

Answers (4)

Joh
Joh

Reputation: 2380

I have difficulties conceiving a meaningful problem with decreasing complexity. A "meaningful" problem will need to read or touch parts of all of its input. Unless the input is encoded in a very inefficient way, processing it should take an increasing amount of time.

It could be increasing toward a constant, though.

Upvotes: 2

Anurag
Anurag

Reputation: 141899

Use any inverse function.

f(x) -> 1 / x
f(x) -> 1 / x²
f(x) -> 1 / log(x)

As the input x grows, the resulting value will get smaller. It's fairly straightforward to relate a smaller value to lesser number of steps in the algorithm. Just use a counter in a loop to move towards that number.

Here's a simple algorithm.

function(x) {
    step = 0.001
    y = 1 / x;
    for (i = 0; i < y; i += step) { /* do something awesome here */ }
}

Upvotes: 3

Ryan Culpepper
Ryan Culpepper

Reputation: 10663

The average running time of SAT for randomly-generated 3CNF clauses eventually goes down as the ratio of clauses to variables increases. The intuition is that when there are very many clauses relative to the number of variables, it is more likely that the formula is "obviously" unsatisfiable; that is, typical SAT-solving algorithms (a step or two better than exhaustive search, but simple enough to cover in an undergrad logic course) quickly reach contradictions and stop.

Of course, those are experimental observations for some notion of "random" 3CNF formulas. I'm not sure what people have proven about it.

Upvotes: 5

Svante
Svante

Reputation: 51531

The Boyer-Moore string search algorithm gets faster when the string searched for gets longer. Of course, the limiting factor is most often rather the length of the string searched in.

Upvotes: 16

Related Questions