(0) Obligation:

Need to prove time_complexity of the following program:
package example_3;

public class Test {
	int i;

	/**
	 * Same simple arithmetic loop, but the loop counter
	 * is a numeric field.
	 */
	public void m(int n) {
		while (i < n) {
			i++;
		}
	}

	public static void main() {
		Test o = new Test();
		o.m(10);
	}

}


(1) JBCToGraph (BOTH CONCRETE BOUNDS(ID, ID) transformation)

Constructed TerminationGraph.

(2) Obligation:

Termination Graph based on JBC Program:
example_3.Test.main()V: Graph of 150 nodes with 0 SCCs.


(3) TerminationGraphToComplexityProof (EQUIVALENT transformation)

Proven constant complexity by absence of SCCs and edges with non-constant weight

(4) BOUNDS(CONSTANT, 141)

(5) JBCToGraph (BOTH CONCRETE BOUNDS(ID, ID) transformation)

Constructed TerminationGraph.

(6) Obligation:

Termination Graph based on JBC Program:
example_3.Test.main()V: Graph of 64 nodes with 1 SCC.


(7) TerminationGraphToComplexityProof (BOTH CONCRETE BOUNDS(ID, ADD(3)) transformation)

Extracted set of 61 edges for the analysis of TIME complexity. Kept leaves.

(8) Obligation:

Set of 61 edges based on JBC Program.
Performed SCC analyses:
  • Used field analysis yielded the following read fields:
    • example_3.Test: [i]

Considered paths: nonterm paths and paths from start to sinks

(9) TerminationGraphToComplexityProof (BOTH CONCRETE BOUNDS(ID, ADD(3)) transformation)

Extracted set of 60 edges for the analysis of TIME complexity. Dropped leaves.

(10) Obligation:

Set of 60 edges based on JBC Program.
Performed SCC analyses:
  • Used field analysis yielded the following read fields:
    • example_3.Test: [i]

Considered paths: all paths from start