usefulweb.site Big-O Crossover Calculator

Math & science

Big-O Crossover Calculator

When does c₁·n log n beat c₂·n²? Crossover points, log-log chart and run times.

Cost functions (required)
Cost functions
#NameGrowthConstant ck (for n^k)
1
2
3
4

For converting cost into time; 10^9 is a rough figure for simple operations on one CPU core.

Try an example: Merge sort vs insertion sort · Brute force 2ⁿ vs n³ dynamic programming

How it works

Compares cost functions such as 50·n log n against 2·n² or 2ⁿ with your constant factors, finds every input size where one overtakes another, draws them on a log-log chart, and converts operation counts into running time at a given number of operations per second.

  • Each cost is c·f(n) with log₂ for logarithms; n! is evaluated as Γ(n + 1), so every function is continuous in n. All comparisons are done on log10 of the cost, so 2ⁿ or n! for large n never overflow.
  • Crossovers: the difference of the log costs is sampled at 2,000 log-spaced sizes between the smallest and largest n; every sign change is refined by 80 bisection steps. Crossovers closer together than the grid spacing can be missed.
  • Time = cost ÷ operations per second. Real programs also depend on memory access, caches and constant overheads that a single constant c only approximates.

Sources

  • Knuth, D. E. (1976): Big Omicron and big Omega and big Theta (SIGACT News 8(2))

For scripts and AI agents

  • JSON API: POST https://bigocrossovercalculator.usefulweb.site/api/v1/calculate (same calculation as this page)
  • Interface description: OpenAPI 3.1 · AI guide: llms.txt
  • MCP server (Streamable HTTP): https://bigocrossovercalculator.usefulweb.site/mcp · tool name big_o_crossover_calculator
Example request
curl -s -X POST https://bigocrossovercalculator.usefulweb.site/api/v1/calculate \
  -H 'content-type: application/json' \
  -d '{"functions":[{"label":"Merge sort","complexity":"nlogn","constant":6},{"label":"Insertion sort","complexity":"n2","constant":0.5}]}'

Related tools

Feedback