Traveling Salesman Problem: Big O Complexity of Algorithm I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused.


  The Traveling Salesman problem (TSP) is famous.  Given a list of
  cities and the distances in between them, the task is to find the
  shortest possible ​tour​ that starts at a city, visits each city
  exactly once and returns to a starting city. A particular tour can be
  described as list of all cities [c1,c2, c3, ... ,cn] ordered by the
  position in which they are visited with the assumption that you return
  from the last city to the start.This is a hard problem, that is, there
  is no known efficient solution for this problem and we are not
  expecting one any time soon. Your task is to analyze the following
  brute force approach to solving the problem:
  
  Consider the following algorithm for solving the TSP:

n = number of cities
m = n x n matrix of distances between cities
min = (infinity)
for all possible tours do:
    find the length of the tour
    if length &lt; min:
         min = length
         store tour

  
  State the worst-case (big-O) complexity of this algorithm in terms of
  ​​(number of cities)?You may assume that matrix lookup is one step
  O(1). For deriving big-O here, you need not count the if-statement or
  the for-loop conditional (i.e., testing to see when the for-loop is
  done), or any of the initializations at the start of the algorithm.


So far I know that there are 2 statements that will be executed after the if statement and I think there n! permutations of tours. Am I correct so far. How would I figure out the amounts of steps for "find the length of tour"?
You've almost got it! Remember, you're going to visit each city exactly once in a tour. Which means you have to look up $n-1$ distances for each one. This is $O(n)$, since the problem specifies that matrix lookup is assumed to be $O(1)$.