5
\$\begingroup\$

In 256 bytes or fewer write a function, \$f\$, from the positive integers to the positive integers that is:

  • Monotonic: larger inputs always map to larger outputs. (\$a < b \implies f(a) < f(b)\$)

  • Non-linear: does not have asymptotic order notation \$O(n)\$. (\$\displaystyle\forall c: \exists n:c\cdot n < f(n)\$)

Your answers will be scored by the asymptotic Big-O order notation of the function they implement (run time is irrelevant) with smaller being better. In the case of a tie the size of the code is the tie breaker.

You may implement a function or a complete program. Since we are concerned with asymptotic complexity your program should accept input of arbitrary size.

\$\endgroup\$
14
  • 1
    \$\begingroup\$ Perhaps a metric what combines O(n) of the function and code length would be better? Currently it may be too easy to outscore any answer that doesn't use all 256 bytes \$\endgroup\$ – Luis Mendo Jul 7 '19 at 17:12
  • 1
    \$\begingroup\$ How are language value bit-size limitations handled? Eg. this program works, but if the ... is repaced with YYY, it breaks down due to the limitations on floating point numbers. Mathematically the second function should be 1,000,000,000 times closer to linear than the first, and every additional Y makes it closer still, but due to computational limits, the intermediate values exceed the available bit-space and precision is lost. \$\endgroup\$ – Draco18s no longer trusts SE Jul 7 '19 at 17:24
  • 3
    \$\begingroup\$ Just nitpicking: 1) Would the term supra-linear perhaps be better suited to the mathematical description you gave? (for example, a logarithmic function is non-linear but doesn't match the alternate definition) 2) Doesn't (strict) monotonicity (as you chose to define it using \$<\$) imply injectivity? \$\endgroup\$ – Mr. Xcoder Jul 7 '19 at 17:32
  • 1
    \$\begingroup\$ @Mr.Xcoder You will find that there is no monotonic positive integer function can be less than linear. You are right about the injectivity though. \$\endgroup\$ – Wheat Wizard Jul 7 '19 at 17:37
  • 1
    \$\begingroup\$ @pppery Actually, g(x) = x * f(x). \$\endgroup\$ – jimmy23013 Jul 8 '19 at 17:35

Browse other questions tagged or ask your own question.