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

Question

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

Answer 1

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.

Answer 2

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.