# Properties By [[Average Case Time Complexity of Randomized Max-Cut Approximation Algorithm]], asserts that the average-case time complexity is at most $(m+2)/2$ where $m$ is the number of edges.