estimate_complexity

Builtin index · REPL & diagnostics

result = estimate_complexity(sizes, times)

Input: sizes, times · Output: result

What it is

Takes two same-length numeric vectors/lists: sizes (the problem sizes swept over) and times (the matching elapsed times in seconds, e.g. from toc() at each size) — at least 3 matching points are required in both. Fits several candidate growth models (O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3)) to the data by least squares and picks whichever has the best R², rather than a naive log-log slope (which misclassifies O(log n)/O(n log n)). As a side effect it prints the fit (label, R², coefficient); it also returns the label as a string (e.g. "O(n)"). Meant to pair with tic/toc: sweep over increasing problem sizes, record elapsed time at each, then call this on the two vectors.

Overloads

One call shape — this function is not overloaded.

Examples

From the documentation, and run by the build -- the output and the figure below are what the engine actually produced. Simplest first.

sizes = [100, 1000, 10000, 100000]
times = []
for n in sizes
    tic()
    total = 0
    for j in 1 to n
        total = total + j
    end
    dt = toc()
    times = append(times, dt)
end
label = estimate_complexity(sizes, times)   # e.g. "O(n)"

print("estimated complexity label = {label}")

from repl-diagnostics

How it works

estimate_complexity(sizes, times) — empirical Big-O: fits several candidate growth models (O(1)/O(log n)/O(n)/ O(n log n)/O(n^2)/O(n^3)) by least squares and reports whichever has the best R^2, not a naive log-log slope (which misclassifies O(log n)/O(n log n) — see best_complexity_fit). Pair with tic/toc: run your own sweep over increasing problem sizes, record the elapsed time at each, then call this on the two vectors.

From the note above this builtin in the interpreter, where the reasoning was written down as it was built.