details

property	value
status	complete
benchmark	realheapsort_step1.koat
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n070.star.cs.uiowa.edu
space	WTC

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	16.8375 seconds
cpu usage	23.0463
user time	22.5149
system time	0.531335
max virtual memory	1.8533444E7
max residence set size	270352.0

stage attributes

key	value
starexec-result	WORST_CASE(?, O(n^2))

output

22.90/16.79 WORST_CASE(?, O(n^2)) 22.97/16.80 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 22.97/16.80 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 22.97/16.80 22.97/16.80 22.97/16.80 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, max(5, 5 + Arg_0) + nat(3 * Arg_0^2) + max(2 * Arg_0 * max(6, 6 + 6 * Arg_0^2), 2 * Arg_0 * max(max(6, 6 + 6 * Arg_0^2), 6), 0) + max(Arg_0 * max(5, max(5, 5 + 4 * Arg_0^2)), Arg_0 * max(5, 5 + 4 * Arg_0^2), 0)). 22.97/16.80 22.97/16.80 (0) CpxIntTrs 22.97/16.80 (1) Koat Proof [FINISHED, 387 ms] 22.97/16.80 (2) BOUNDS(1, n^2) 22.97/16.80 (3) Koat2 Proof [FINISHED, 3042 ms] 22.97/16.80 (4) BOUNDS(1, max(5, 5 + Arg_0) + nat(3 * Arg_0^2) + max(2 * Arg_0 * max(6, 6 + 6 * Arg_0^2), 2 * Arg_0 * max(max(6, 6 + 6 * Arg_0^2), 6), 0) + max(Arg_0 * max(5, max(5, 5 + 4 * Arg_0^2)), Arg_0 * max(5, 5 + 4 * Arg_0^2), 0)) 22.97/16.80 (5) Loat Proof [FINISHED, 15.0 s] 22.97/16.80 (6) BOUNDS(1, INF) 22.97/16.80 22.97/16.80 22.97/16.80 ---------------------------------------- 22.97/16.80 22.97/16.80 (0) 22.97/16.80 Obligation: 22.97/16.80 Complexity Int TRS consisting of the following rules: 22.97/16.80 evalrealheapsortstep1start(A, B, C) -> Com_1(evalrealheapsortstep1entryin(A, B, C)) :|: TRUE 22.97/16.80 evalrealheapsortstep1entryin(A, B, C) -> Com_1(evalrealheapsortstep1bb6in(A, 1, C)) :|: A >= 3 22.97/16.80 evalrealheapsortstep1entryin(A, B, C) -> Com_1(evalrealheapsortstep1returnin(A, B, C)) :|: 2 >= A 22.97/16.80 evalrealheapsortstep1bb6in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, B)) :|: A >= 1 + B 22.97/16.80 evalrealheapsortstep1bb6in(A, B, C) -> Com_1(evalrealheapsortstep1returnin(A, B, C)) :|: B >= A 22.97/16.80 evalrealheapsortstep1bb3in(A, B, C) -> Com_1(evalrealheapsortstep1bb5in(A, B, C)) :|: 0 >= C 22.97/16.80 evalrealheapsortstep1bb3in(A, B, C) -> Com_1(evalrealheapsortstep1bb4in(A, B, C)) :|: C >= 1 22.97/16.80 evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb2in(A, B, C)) :|: C + 1 >= 0 && C + 1 <= 0 22.97/16.80 evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb2in(A, B, C)) :|: C >= 0 && D >= 0 && C + 1 >= 2 * D && 2 * D >= C 22.97/16.80 evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb2in(A, B, C)) :|: 0 >= C + 2 && 0 >= D && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb5in(A, B, C)) :|: C + 1 >= 0 && C + 1 <= 0 22.97/16.80 evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb5in(A, B, C)) :|: C >= 0 && D >= 0 && C + 1 >= 2 * D && 2 * D >= C 22.97/16.80 evalrealheapsortstep1bb4in(A, B, C) -> Com_1(evalrealheapsortstep1bb5in(A, B, C)) :|: 0 >= C + 2 && 0 >= D && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: C + 1 >= 0 && C + 1 <= 0 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && C + 1 >= 0 && C + 1 <= 0 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && 0 >= D && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && C + 1 >= 0 && C + 1 <= 0 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && C + 1 >= 0 && C + 1 <= 0 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && 0 >= D && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && 0 >= D && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && 0 >= E && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= 1 && 0 >= E && 0 >= D && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && C + 1 >= 0 && C + 1 <= 0 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && D >= 0 && C + 1 >= 2 * D && 2 * D >= C 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && 0 >= C + 2 && 0 >= D && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && D >= 0 && 0 >= 2 * D && 1 + 2 * D >= 0 && 0 >= E && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && 0 >= C + 2 && 0 >= F && D >= 0 && C + 1 >= 2 * D && 2 * D >= C && 2 * F >= C + 1 && 2 + C >= 2 * F 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && 0 >= C + 2 && 0 >= F && 0 >= D && 2 * F >= C + 1 && 2 + C >= 2 * F && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && 0 >= D && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= C + 2 && 0 >= E && C >= 0 && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && D >= 0 && C + 1 >= 2 * D && 2 * D >= C && 2 * E >= C + 1 && 2 + C >= 2 * E 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= C + 2 && 0 >= E && C >= 0 && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && 0 >= D && 2 * E >= C + 1 && 2 + C >= 2 * E && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, -(1))) :|: 0 >= 1 && 0 >= D && 0 >= E && C + 1 >= 0 && C + 1 <= 0 && 2 * D >= C + 1 && 2 + C >= 2 * D && 2 * E >= C + 1 && 2 + C >= 2 * E 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= C + 2 && 0 >= E && 0 >= F && C >= 0 && D >= 0 && C + 1 >= 2 * D && 2 * D >= C && 2 * E >= C + 1 && 2 + C >= 2 * E && 2 * F >= C + 1 && 2 + C >= 2 * F 22.97/16.80 evalrealheapsortstep1bb2in(A, B, C) -> Com_1(evalrealheapsortstep1bb3in(A, B, D - 1)) :|: 0 >= C + 2 && 0 >= E && 0 >= F && 0 >= D && 2 * E >= C + 1 && 2 + C >= 2 * E && 2 * F >= C + 1 && 2 + C >= 2 * F && 2 * D >= C + 1 && 2 + C >= 2 * D 22.97/16.80 evalrealheapsortstep1bb5in(A, B, C) -> Com_1(evalrealheapsortstep1bb6in(A, B + 1, C)) :|: TRUE 22.97/16.80 evalrealheapsortstep1returnin(A, B, C) -> Com_1(evalrealheapsortstep1stop(A, B, C)) :|: TRUE 22.97/16.80 22.97/16.80 The start-symbols are:[evalrealheapsortstep1start_3] 22.97/16.80 22.97/16.80 22.97/16.80 ---------------------------------------- 22.97/16.80 22.97/16.80 (1) Koat Proof (FINISHED) 22.97/16.80 YES(?, 36*ar_0^2 + 841*ar_0 + 1545) 22.97/16.80 22.97/16.80 22.97/16.80 22.97/16.80 Initial complexity problem: 22.97/16.80 22.97/16.80 1: T: 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1start(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1entryin(ar_0, ar_1, ar_2)) 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb6in(ar_0, 1, ar_2)) [ ar_0 >= 3 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1entryin(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ 2 >= ar_0 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, ar_1)) [ ar_0 >= ar_1 + 1 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb6in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1returnin(ar_0, ar_1, ar_2)) [ ar_1 >= ar_0 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb3in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2)) [ ar_2 >= 1 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 + 1 = 0 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 + 2 /\ 0 >= d /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 + 1 = 0 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ ar_2 >= 0 /\ d >= 0 /\ ar_2 + 1 >= 2*d /\ 2*d >= ar_2 ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb4in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb5in(ar_0, ar_1, ar_2)) [ 0 >= ar_2 + 2 /\ 0 >= d /\ 2*d >= ar_2 + 1 /\ ar_2 + 2 >= 2*d ] 22.97/16.80 22.97/16.80 (Comp: ?, Cost: 1) evalrealheapsortstep1bb2in(ar_0, ar_1, ar_2) -> Com_1(evalrealheapsortstep1bb3in(ar_0, ar_1, -1)) [ ar_2 + 1 = 0 ] 22.97/16.80 popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to Complexity_ITS 2019-03-21 04.46