Some I O complexity bounds

Problem	Upper Bound (Deterministic)	Upper Bound (Randomized)	Lower Bound
Maximal Independent Set		O(sort(E) [1]
Maximal Matching	O(sort(E)) + E/V sort(V) log(V/M)) [1]	O(sort(E)) [1]

[1]