CODEWITHSUNDEEP
algorithmgraphtime-complexitygraph-algorithm
Thomas
Thomas

Reputation: 613

Hamiltonian Path Algorithm Time-Complexity

I am writing a program searching for Hamiltonian Paths in a Graph. It works by searching all possible permutations between the vertices of the graph, and then by checking if there is an edge between all consecutive vertices in each permutation.

I calculated the time-complexity to be O(n)=n!*n^2.

To calculate the time-complexity I thought : to calculate each permutation, I loop through the list of vertices. What's more there is n! permutations, and then for each permutation I loop again through the list of vertices to check if there is an edge between two consecutive vertices. So this makes O(n)=n!*n*n.

Did I make a mistake in this calculation ?

I think I made a mistake, because I measured the time for the program to execute for different sizes of graphs, and the complexity looks more like O(n)=n!

Here are some values of how much time the program took to execute, with n the number of vertices in the graph.

On a Machine with 3.5GHz i7 Processor and 16 GB RAM:
n=2 : 0.000025 s
n=3 : 0.000041 s
n=4 : 0.00013 s
n=5 : 0.00065 s
n=6 : 0.0045 s
n=7 : 0.039 s
n=8 : 0.31 s
n=9 : 3.2 s
n=10 : 36 s
n=11 : 455 s

Here is my code :

main

graph=Graph([[1,4],[0,2,3],[1,3],[1,2,4],[0,3]]) #n = 5 (number of nodes)
ham = hamiltonianPaths0(graph)

hamiltonianPaths0 function

def hamiltonianPaths0(graph, circuit=False):
    name = "circuit" if circuit else "path"
    f=0
    paths=[]
    for i in permutations(graph.vertices):
        k=1
        for j in range(len(i)-1+int(circuit)):
            if [i[j],i[(j+1)%len(i)]] in graph.edges:
                #print("Edge from {} to {}".format(i[j], i[(j+1)%len(i)]))
                k+=1
            if k==len(i)+int(circuit):
                print("{} is a hamiltonian {} !".format(i,name))
                f+=1
                paths.append(i)

    print("{} hamiltonian {}(s) found !".format(f,name))
    return paths

permutations function

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

PS : the graph class makes a graph from a list specifying for each vertex with which other vertex it is linked. for example : Graph([[1],[0,2],[1]]) will produce a graph with 3 vertex (0,1,2) with 0 linked to 1, 1 linked to 0 and 2 and 2 linked to 1). And Graph.vertices is a list containing all the vertices of a graph.

Upvotes: 2

Views: 7839

Answers (1)

Prune
Prune

Reputation: 77847

O(n!) and O(n! * n^2) are the same complexity. Let's "overshoot" by a lower-order amount on the right side of this and reduce the expression.

n! * n * n <= n! * (n+1) * (n+2)
n! * n * n <= (n+2)!

However, O(n!) == O((n+2)!)

Q.E.D.

Upvotes: 0

Related Questions