I have a heuristic algorithm (not randomized!) to find solutions in a
combinatorial problem. What is the best way to prove/evaluate the
algorithm (correctness, completeness, perfomrance, average distance of
results to global optimum).

I thought about fitness landscapes, but my real-life-problem is
NP-hard and even with less input data the search space becomes huge.
So, I cant calculate the fitness landscape of such a problem.

My question: What else can I do?