I think the problem can be separated into two:
1. Guarantee a given Big O complexity of a function, (that's what
matters for most cases),
2. Guarantee / tell the worst case execution time / CPU cycles of
a given @constanttime function.
Combining these two, we can calculate the worst case execition
time for the full program.
@constanttime can have branches, each branch with different worst
case execution time, it won't change the @constanttime nature of
the funcion. (But makes it harder to calculate the worst case
execution time, and the average case and the worst case won't be
the same.)
@constanttime could also have loops / recursion, if the number of
iterations / recursion is limited. I.e. sorting 5 numbers during
the median of 5 algorithm is @constanttime, even if it calls a
sort function which is O(N log N). I.e. this is valid:
@constanttime auto sort5(Range)(Range values)
{
assert(values.length <= 5);
return values.bubblesort();
}
/* inferred: @quadratic */ int[] bubblesort(int[] values) {
for (int i=0; i<values.length; i++)
for (int j=i+1; j<values.length; j++)
if (values[j] < values[i])
swap(values[i], values[j]);
}
If the number of iteration in a function is proportional to the
input's length, then it's @linear or @BigO_N. If there are two
such iterations nested, then it's @quadratic or @BigO_N2, and so
on.
These could be very well inferred and guaranteed by the compiler.
But the Compiler might not realize that the amortized time is
less than what it looks like from the first glance. So the user
could annotate a function inferred as @quadratic as @linear. Then
the linearity of the function could be validated / guaranteed
during runtime using the amortization credit system: the function
should allocate credits based on the input size and its promise,
then use this credit to call @constattime functions, while not
running out of credits. These credits could be passed-on to
@linear functions as well, those will use more credits, according
their input sizes. If the promise is broken and the program runs
out of credit, it should break immediately. This validation could
be turned off, similar to assert calls.
