. Since is smaller than , there is some element of which can be put into with the result still being independent. However is an element of maximal weight that can be added to to maintain independence. Thus is of no smaller weight than some element of , and hence is of at least a large a weight as . As this is true for all , is weightier than . Complexity analysis The easiest way to traverse the members of in the desired order is to sort them. This requires time using a comparison sorting algorithm. We also need to test for each whether is independent; assuming independence tests require time, the total time for the algorithm is . If we want to find a minimum spanning tree instead, we simply "invert" the weight function by subtracting it from a large constant. More specifically, let , where exceeds the total weight over all graph edges. Many more optimization problems about all sorts of matroids and weight functions can be solved in this trivial way, although in many cases more efficient algorithms can be found that exploit more specialized properties. Matroid requirement Note also that if we take a set of "independent" sets which is a down-set but not a matroid, then the greedy algorithm will not always work. For then there are independent sets and with , but such that for no is independent. Pick an and such that . Weight the elements of in the range to , the elements of in the range to , the elements of in the range to , and the rest in the range to . The greedy algorithm will select the elements of , and then cannot pick any elements of . Therefore, the independent set it constructs will be of weight at most , which is smaller than the weight of . History It was not until 1971 that Jack Edmonds connected weighted matroids to greedy algorithms in his paper "Matroids and the greedy algorithm". Korte and Lovász would generalize these ideas to objects called greedoids, which allow even larger classes of problems to be solved by greedy algorithms. References Jack Edmonds. Matroids and the Greedy Algorithm. Mathematical Programming, volume 1, p. 125–136. 1971. Matroid theory