What is the computational complexity of tabu search?

Question

I was wondering what the computational complexity of a metaheuristic like tabu search. Why there is not a section to discuss the time and space complexity of the algorithm in the original paper and even on the improvement of the algorithm like iterative tabu search and reactive tabu search?

I want to analyze the algorithm with others on the travelling salesman problem.

begin
 T:= [ ];
 s:=initial solution;
 s*:=s
 repeat
 find the best admissible s’ є N(s);
 if f(s’) > f(s*) then s*:=s’
 s:=s’;
 update tabu list T;
 until stopping criterion:
end;

Answer 1

This algorithm is not population-base algorithms. this do is very similar to a typical derivation, so it does not matter how to execute it in finding the very important problem. It is true that in previous scientific discussions there has not been much talk about this issue because several algorithms have been developed to solve a problem that works better than tabu algorithm.