(0) Obligation:

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

public class ArrayPrimitives {
	public static void main(String[] argv) {
		Random.args = argv;
		int int0 = Random.random();
		int int1 = Random.random();
		int int2 = Random.random();
		int[] data = {int0, int1, int2};
		while (data[0] != int0);
		while (data[1] != int1);
		while (data[2] != int2);
	}
}


package ArrayPrimitives;

public class Random {
  static String[] args;
  static int index = 0;

  public static int random() {
    String string = args[index];
    index++;
    return string.length();
  }
}


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

Constructed TerminationGraph.

(2) Obligation:

Termination Graph based on JBC Program:
ArrayPrimitives.ArrayPrimitives.main([Ljava/lang/String;)V: Graph of 252 nodes with 0 SCCs.


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

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

(4) Obligation:

Set of 79 edges based on JBC Program.
Performed SCC analyses:
  • Used field analysis yielded the following read fields:

Considered paths: nonterm paths and paths from start to sinks

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

Constructed TerminationGraph.

(6) Obligation:

Termination Graph based on JBC Program:
ArrayPrimitives.ArrayPrimitives.main([Ljava/lang/String;)V: Graph of 252 nodes with 0 SCCs.


(7) TerminationGraphToComplexityProof (EQUIVALENT transformation)

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

(8) BOUNDS(CONSTANT, 225)