In this section, we analyse the run-time complexity for SGP-opt. As we can see from the example in section 5.6.3, the reduction of instances of IP produces a certain type of graph that has only edges between adjacent vertices. We denote such graphs as IP-graphs . Actually, this property can be exploited nicely to reduce the run time complexity of SGP-opt as we will see by proving the following
Theorem 29104
The run-time complexity of SGP-opt is O(n3) in the general case and O(n2) for IP-graphs as imposed by the interval partitioning (IP) problem if n is the number of vertices in the graph.
Assume a graph G=(V,A) and let n=|V|. The run-time complexity of SGP-opt is determined by the following steps:
The generation of and depend on the type of the graph:
General case: The general definitions of and are as follows:
which can be done by scanning the set A of edges and adding the lengths if the indices i,j satisfy .Thus computing is O(|A|) and doing it for is which is at most O(n3) as . This allows us to derive a recursive equation which can obviously be computed in O(n) and so it takes O(n3) time to do it for all pairs of x,y with x<y.Thus the general case produces partial complexities , O(n3), O(1), O(n2), O(n) which evolves to O(n3) in total.
IP-graphs: The IP-graph property of l(vi,vj)=0 for all allows to compute
in O(1) and in O(n) for all x, and in O(1) and in O(n2) for all x,y.Thus the general case produces partial complexities O(n), O(n2), O(1), O(n2), O(n) which evolves to O(n2) in total.