Traveling Salesman Problem: Big O Complexity of Algorithm
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)$.