MAYBE Initial complexity problem: 1: T: (1, 1) f3(a, b, c) -> f2(a, b, c) (?, 1) f2(a, b, c) -> f2(e - 1, b, c) [ 0 >= a + 1 /\ 0 >= d /\ b >= 1 ] (?, 1) f2(a, b, c) -> f2(e - 1, b, c) [ 0 >= a + 1 /\ 0 >= d /\ 0 >= b ] (?, 1) f2(a, b, c) -> f2(e + 1, b, c) [ d >= 2 /\ 0 >= a + 1 ] (?, 1) f2(a, b, c) -> f2(e - 1, b, c) [ a >= 1 /\ 0 >= d + 2 /\ b >= 1 ] (?, 1) f2(a, b, c) -> f2(e - 1, b, c) [ a >= 1 /\ 0 >= d + 2 /\ 0 >= b ] (?, 1) f2(a, b, c) -> f2(e + 1, b, c) [ d >= 0 /\ a >= 1 ] (?, 1) f2(a, b, c) -> f300(0, b, e) [ 0 >= a + 1 ] (?, 1) f2(a, b, c) -> f300(0, b, e) [ a >= 1 ] (?, 1) f2(a, b, c) -> f300(a, b, e) [ a = 0 ] start location: f3 leaf cost: 0 Repeatedly removing leaves of the complexity graph in problem 1 produces the following problem: 2: T: (1, 1) f3(a, b, c) -> f2(a, b, c) (?, 1) f2(a, b, c) -> f2(e - 1, b, c) [ 0 >= a + 1 /\ 0 >= d /\ b >= 1 ] (?, 1) f2(a, b, c) -> f2(e - 1, b, c) [ 0 >= a + 1 /\ 0 >= d /\ 0 >= b ] (?, 1) f2(a, b, c) -> f2(e + 1, b, c) [ d >= 2 /\ 0 >= a + 1 ] (?, 1) f2(a, b, c) -> f2(e - 1, b, c) [ a >= 1 /\ 0 >= d + 2 /\ b >= 1 ] (?, 1) f2(a, b, c) -> f2(e - 1, b, c) [ a >= 1 /\ 0 >= d + 2 /\ 0 >= b ] (?, 1) f2(a, b, c) -> f2(e + 1, b, c) [ d >= 0 /\ a >= 1 ] start location: f3 leaf cost: 3 Complexity upper bound ? Time: 0.354 sec (SMT: 0.331 sec)