details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	42.1318 seconds
cpu usage	57.2419
user time	56.0932
system time	1.14874
max virtual memory	1.8822176E7
max residence set size	288352.0

stage attributes

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

output

57.14/42.09 WORST_CASE(?, O(n^2)) 57.14/42.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.koat 57.14/42.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 57.14/42.11 57.14/42.11 57.14/42.11 The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(1, n^2). 57.14/42.11 57.14/42.11 (0) CpxIntTrs 57.14/42.11 (1) Koat Proof [FINISHED, 1281 ms] 57.14/42.11 (2) BOUNDS(1, n^2) 57.14/42.11 57.14/42.11 57.14/42.11 ---------------------------------------- 57.14/42.11 57.14/42.11 (0) 57.14/42.11 Obligation: 57.14/42.11 Complexity Int TRS consisting of the following rules: 57.14/42.11 evalrealheapsortstart(A, B, C, D) -> Com_1(evalrealheapsortentryin(A, B, C, D)) :|: TRUE 57.14/42.11 evalrealheapsortentryin(A, B, C, D) -> Com_1(evalrealheapsortbb6in(A, 1, C, D)) :|: A >= 3 57.14/42.11 evalrealheapsortentryin(A, B, C, D) -> Com_1(evalrealheapsortreturnin(A, B, C, D)) :|: 2 >= A 57.14/42.11 evalrealheapsortbb6in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, B, D)) :|: A >= 1 + B 57.14/42.11 evalrealheapsortbb6in(A, B, C, D) -> Com_1(evalrealheapsortbb7in(A, B, C, D)) :|: B >= A 57.14/42.11 evalrealheapsortbb3in(A, B, C, D) -> Com_1(evalrealheapsortbb5in(A, B, C, D)) :|: 0 >= C 57.14/42.11 evalrealheapsortbb3in(A, B, C, D) -> Com_1(evalrealheapsortbb4in(A, B, C, D)) :|: C >= 1 57.14/42.11 evalrealheapsortbb4in(A, B, C, D) -> Com_1(evalrealheapsortbb2in(A, B, C, D)) :|: C + 1 >= 0 && C + 1 <= 0 57.14/42.11 evalrealheapsortbb4in(A, B, C, D) -> Com_1(evalrealheapsortbb2in(A, B, C, D)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C 57.14/42.11 evalrealheapsortbb4in(A, B, C, D) -> Com_1(evalrealheapsortbb2in(A, B, C, D)) :|: 0 >= C + 2 && 0 >= E && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb4in(A, B, C, D) -> Com_1(evalrealheapsortbb5in(A, B, C, D)) :|: C + 1 >= 0 && C + 1 <= 0 57.14/42.11 evalrealheapsortbb4in(A, B, C, D) -> Com_1(evalrealheapsortbb5in(A, B, C, D)) :|: C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C 57.14/42.11 evalrealheapsortbb4in(A, B, C, D) -> Com_1(evalrealheapsortbb5in(A, B, C, D)) :|: 0 >= C + 2 && 0 >= E && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, -(1), D)) :|: C + 1 >= 0 && C + 1 <= 0 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= 1 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && C + 1 >= 0 && C + 1 <= 0 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= 1 && 0 >= E && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, -(1), D)) :|: 0 >= 1 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && C + 1 >= 0 && C + 1 <= 0 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= 1 && F >= 0 && 0 >= 2 * F && 1 + 2 * F >= 0 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && C + 1 >= 0 && C + 1 <= 0 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= 1 && F >= 0 && 0 >= 2 * F && 1 + 2 * F >= 0 && 0 >= E && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, -(1), D)) :|: 0 >= 1 && 0 >= E && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= 1 && 0 >= F && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && C + 1 >= 0 && C + 1 <= 0 && 2 * F >= C + 1 && 2 + C >= 2 * F 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= 1 && 0 >= F && 0 >= E && C + 1 >= 0 && C + 1 <= 0 && 2 * F >= C + 1 && 2 + C >= 2 * F && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, -(1), D)) :|: 0 >= 1 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && F >= 0 && 0 >= 2 * F && 1 + 2 * F >= 0 && C + 1 >= 0 && C + 1 <= 0 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: C >= 0 && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && G >= 0 && C + 1 >= 2 * G && 2 * G >= C && E >= 0 && C + 1 >= 2 * E && 2 * E >= C 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: C >= 0 && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && G >= 0 && C + 1 >= 2 * G && 2 * G >= C && 0 >= C + 2 && 0 >= E && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, -(1), D)) :|: 0 >= 1 && E >= 0 && 0 >= 2 * E && 1 + 2 * E >= 0 && 0 >= F && C + 1 >= 0 && C + 1 <= 0 && 2 * F >= C + 1 && 2 + C >= 2 * F 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: C >= 0 && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && 0 >= C + 2 && 0 >= G && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && 2 * G >= C + 1 && 2 + C >= 2 * G 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: C >= 0 && F >= 0 && C + 1 >= 2 * F && 2 * F >= C && 0 >= C + 2 && 0 >= G && 0 >= E && 2 * G >= C + 1 && 2 + C >= 2 * G && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, -(1), D)) :|: 0 >= 1 && 0 >= E && F >= 0 && 0 >= 2 * F && 1 + 2 * F >= 0 && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= C + 2 && 0 >= F && C >= 0 && G >= 0 && C + 1 >= 2 * G && 2 * G >= C && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && 2 * F >= C + 1 && 2 + C >= 2 * F 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= C + 2 && 0 >= F && C >= 0 && G >= 0 && C + 1 >= 2 * G && 2 * G >= C && 0 >= E && 2 * F >= C + 1 && 2 + C >= 2 * F && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, -(1), D)) :|: 0 >= 1 && 0 >= E && 0 >= F && C + 1 >= 0 && C + 1 <= 0 && 2 * E >= C + 1 && 2 + C >= 2 * E && 2 * F >= C + 1 && 2 + C >= 2 * F 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= C + 2 && 0 >= F && 0 >= G && C >= 0 && E >= 0 && C + 1 >= 2 * E && 2 * E >= C && 2 * F >= C + 1 && 2 + C >= 2 * F && 2 * G >= C + 1 && 2 + C >= 2 * G 57.14/42.11 evalrealheapsortbb2in(A, B, C, D) -> Com_1(evalrealheapsortbb3in(A, B, E - 1, D)) :|: 0 >= C + 2 && 0 >= F && 0 >= G && 0 >= E && 2 * F >= C + 1 && 2 + C >= 2 * F && 2 * G >= C + 1 && 2 + C >= 2 * G && 2 * E >= C + 1 && 2 + C >= 2 * E 57.14/42.11 evalrealheapsortbb5in(A, B, C, D) -> Com_1(evalrealheapsortbb6in(A, B + 1, C, D)) :|: TRUE 57.14/42.11 evalrealheapsortbb7in(A, B, C, D) -> Com_1(evalrealheapsortbb18in(A, 0, C, D)) :|: TRUE 57.14/42.11 evalrealheapsortbb18in(A, B, C, D) -> Com_1(evalrealheapsortbb8in(A, B, C, D)) :|: A >= 2 + B 57.14/42.11 evalrealheapsortbb18in(A, B, C, D) -> Com_1(evalrealheapsortreturnin(A, B, C, D)) :|: B + 1 >= A 57.14/42.11 evalrealheapsortbb8in(A, B, C, D) -> Com_1(evalrealheapsortbb16in(A, B, 0, D)) :|: TRUE 57.14/42.11 evalrealheapsortbb16in(A, B, C, D) -> Com_1(evalrealheapsortbb9in(A, B, C, D)) :|: A >= B + 3 + 2 * C 57.14/42.11 evalrealheapsortbb16in(A, B, C, D) -> Com_1(evalrealheapsortbb17in(A, B, C, D)) :|: 2 * C + 2 + B >= A 57.14/42.11 evalrealheapsortbb9in(A, B, C, D) -> Com_1(evalrealheapsortbb11in(A, B, C, D)) :|: A >= 2 * C + 3 + B && A <= 2 * C + 3 + B 57.14/42.11 evalrealheapsortbb9in(A, B, C, D) -> Com_1(evalrealheapsortbb10in(A, B, C, D)) :|: A >= B + 4 + 2 * C 57.14/42.11 evalrealheapsortbb9in(A, B, C, D) -> Com_1(evalrealheapsortbb10in(A, B, C, D)) :|: 2 * C + 2 + B >= A 57.14/42.11 evalrealheapsortbb10in(A, B, C, D) -> Com_1(evalrealheapsortbb11in(A, B, C, D)) :|: TRUE 57.14/42.11 evalrealheapsortbb10in(A, B, C, D) -> Com_1(evalrealheapsortbb12in(A, B, C, D)) :|: TRUE 57.14/42.11 evalrealheapsortbb11in(A, B, C, D) -> Com_1(evalrealheapsortbb13in(A, B, C, 2 * C + 1)) :|: TRUE 57.14/42.11 evalrealheapsortbb12in(A, B, C, D) -> Com_1(evalrealheapsortbb13in(A, B, C, 2 * C + 2)) :|: TRUE 57.14/42.11 evalrealheapsortbb13in(A, B, C, D) -> Com_1(evalrealheapsortbb14in(A, B, C, D)) :|: TRUE 57.14/42.11 evalrealheapsortbb13in(A, B, C, D) -> Com_1(evalrealheapsortbb16in(A, B, A, D)) :|: TRUE 57.14/42.11 evalrealheapsortbb14in(A, B, C, D) -> Com_1(evalrealheapsortbb16in(A, B, D, D)) :|: TRUE 57.14/42.11 evalrealheapsortbb17in(A, B, C, D) -> Com_1(evalrealheapsortbb18in(A, B + 1, C, D)) :|: TRUE 57.14/42.11 evalrealheapsortreturnin(A, B, C, D) -> Com_1(evalrealheapsortstop(A, B, C, D)) :|: TRUE 57.14/42.11 57.14/42.11 The start-symbols are:[evalrealheapsortstart_4] 57.14/42.11 57.14/42.11 57.14/42.11 ---------------------------------------- 57.14/42.11 57.14/42.11 (1) Koat Proof (FINISHED) 57.14/42.11 YES(?, 18004615*ar_0 + 2100*ar_0^2 + 21602533) 57.14/42.11 57.14/42.11 57.14/42.11 57.14/42.11 Initial complexity problem: 57.14/42.11 57.14/42.11 1: T: 57.14/42.11 57.14/42.11 (Comp: ?, Cost: 1) evalrealheapsortstart(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalrealheapsortentryin(ar_0, ar_1, ar_2, ar_3)) 57.14/42.11 57.14/42.11 (Comp: ?, Cost: 1) evalrealheapsortentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalrealheapsortbb6in(ar_0, 1, ar_2, ar_3)) [ ar_0 >= 3 ] 57.14/42.11 57.14/42.11 (Comp: ?, Cost: 1) evalrealheapsortentryin(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalrealheapsortreturnin(ar_0, ar_1, ar_2, ar_3)) [ 2 >= ar_0 ] 57.14/42.11 57.14/42.11 (Comp: ?, Cost: 1) evalrealheapsortbb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalrealheapsortbb3in(ar_0, ar_1, ar_1, ar_3)) [ ar_0 >= ar_1 + 1 ] 57.14/42.11 57.14/42.11 (Comp: ?, Cost: 1) evalrealheapsortbb6in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalrealheapsortbb7in(ar_0, ar_1, ar_2, ar_3)) [ ar_1 >= ar_0 ] 57.14/42.11 57.14/42.11 (Comp: ?, Cost: 1) evalrealheapsortbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalrealheapsortbb5in(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 ] 57.14/42.11 57.14/42.11 (Comp: ?, Cost: 1) evalrealheapsortbb3in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalrealheapsortbb4in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 1 ] 57.14/42.11 57.14/42.11 (Comp: ?, Cost: 1) evalrealheapsortbb4in(ar_0, ar_1, ar_2, ar_3) -> Com_1(evalrealheapsortbb2in(ar_0, ar_1, ar_2, ar_3)) [ ar_2 + 1 = 0 ] 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