We will now establish that the above working requires no more than fourth degree polynomial time.
777
We have to make two types of calculations
778
a + b -c
779
780
781
782
783
784
785
786
a + b - c - d
Now there are ‘n.C(n,2)’ segments which account for various ‘c’ subtractions also their are ‘n’ points for a + b.
c Maximum calculations could be 2. n.C(n,2) as for one point and one segment we have two calculations.
For ‘n’ points we have 2n calculations. Similarly for C (n, 2) segments we have in total 2n.C(n,2) calculations
787
On similar grounds number of calculations for segment to segment are
788
2 .C(n,2).C(n,2)
789
Order of polynomial P is
790
791
792
793
794
795
796
P =2n. C(n,2)+ 2. [C(n,2)]2
÷ C.n4 + C .n3
÷ C .n4 = O(4) [Order 4]
Further for one point if we have to do these number of calculations i.e. to place one point to its nearest branch for a total on ‘n’ points the total number of calculations would be of the order n.Cn4 = Cn5 =O(5) [Order 5]
c Hamiltonians path problem is solvable in polynomial time of fifth degree at most.
797
798
799
Note the term nearest has special significance here. We join a point to a branch only if it is the nearest to it, otherwise we leave it till it is joined to the better places of the network. This method is useful particularly to avoid branches which need to be modified later. So this careful