What is the time complexity of the Hill Climbing Algorithm? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

Specifically, the Steepest-Ascent Hill Climbing, Stochastic Hill Climbing and Simulated Annealing. The generalized time complexity would be fine too. Thanks.

Answer 1

The methods you list can be interrupted at any time, and return “the best result so far”. Therefore, it only makes sense to talk about the time they take to return the absolute best result (the global maximum).

All the methods you list may fail to reach the global maximum. Therefore, their complexity is O(∞).

Traditional time complexity notions do not make sense for heuristics, only for proper algorithms. Here is a writeup about the difference between the two.