1

I'm having trouble finding the time complexity for Backtracking - Traveling Salesman problem. I tried to search for Hamiltonian cycle's time complexity since Backtracking - Traveling Salesman problem uses it and these are what i found:

I've seen from Abdul Bari's youtube channel that the time complexity for Backtracking - Hamiltonian Cycle is n^n while an answer from one of the questions here in stackoverflow is: n!

n^n Reference: https://www.youtube.com/watch?v=dQr4wZCiJJ4&t=389s

n! Reference: How to calculate time complexity of backtracking algorithm?

I don't really know how to compute for time complexity, can you guys help me to determine the time complexity from this one (This is a Backtracking - Traveling Salesman problem code):

Reference: https://www.geeksforgeeks.org/travelling-salesman-problem-implementation-using-backtracking/

public class GFG{ 

// Function to find the minimum weight  
// Hamiltonian Cycle 
static int tsp(int[][] graph, boolean[] v,  
               int currPos, int n,  
               int count, int cost, int ans)  
{ 

    // If last node is reached and it has a link 
    // to the starting node i.e the source then 
    // keep the minimum value out of the total cost 
    // of traversal and "ans" 
    // Finally return to check for more possible values 
    if (count == n && graph[currPos][0] > 0)  
    { 
        ans = Math.min(ans, cost + graph[currPos][0]); 
        return ans; 
    } 

    // BACKTRACKING STEP 
    // Loop to traverse the adjacency list 
    // of currPos node and increasing the count 
    // by 1 and cost by graph[currPos,i] value 
    for (int i = 0; i < n; i++)  
    { 
        if (v[i] == false && graph[currPos][i] > 0)  
        { 

            // Mark as visited 
            v[i] = true; 
            ans = tsp(graph, v, i, n, count + 1, 
                      cost + graph[currPos][i], ans); 

            // Mark ith node as unvisited 
            v[i] = false; 
        } 
    } 
    return ans; 
} 

// Driver code 
public static void main(String[] args) 
{ 

    // n is the number of nodes i.e. V 
    int n = 4; 

    int[][] graph = {{0, 10, 15, 20}, 
                     {10, 0, 35, 25}, 
                     {15, 35, 0, 30}, 
                     {20, 25, 30, 0}}; 

    // Boolean array to check if a node 
    // has been visited or not 
    boolean[] v = new boolean[n]; 

    // Mark 0th node as visited 
    v[0] = true; 
    int ans = Integer.MAX_VALUE; 

    // Find the minimum weight Hamiltonian Cycle 
    ans = tsp(graph, v, 0, n, 1, 0, ans); 

    // ans is the minimum weight Hamiltonian Cycle 
    System.out.println(ans); 
} 
} 

// This code is contributed by Rajput-Ji
peng
  • 21
  • 2

1 Answers1

1

First, n! = O(n^n) can be proved by n!= n* (n-1) *(n-2) ....

n^n = n * n * n....

clearly n! is bounded by n^n and thus you found that "Hamiltonian Cycle is n^n while an answer from one of the questions here in stackoverflow is n!"

For TSP backtracking you have in the worst case (n-1)! permutation, each has to do n-1 addition to find cost. So (n-1) * (n-1)! --> O(n!)

baba smith
  • 711
  • 7
  • 16
Adnan Rasad Kazi
  • 11
  • 1