Which of the following is NOT a characteristic of greedy algorithms?

The choice indicating that a greedy algorithm guarantees a globally optimal solution is indeed not a characteristic of greedy algorithms. Greedy algorithms typically work by making a series of choices that seem the best at the moment, focusing on local optimization. While this approach can lead to a globally optimal solution in certain problems, it does not guarantee that outcome in all cases.

For instance, in algorithms like Dijkstra’s for finding the shortest path in a weighted graph, the greedy method does yield an optimal solution. However, for many other problems, such as the Knapsack problem or the Traveling Salesman problem, a greedy approach may lead to suboptimal solutions because it does not consider the overall structure of the problem and instead relies on immediate benefits.

In contrast, the other characteristics mentioned—making decisions based only on local information and choosing the best immediate option—are fundamental aspects of greedy algorithms. Their step-by-step problem-solving approach reflects how greedy algorithms iteratively build a solution by choosing the best current choice without reconsidering previous choices.