The assignment problem concerns finding the minimum-cost perfect matching in a complete weighted n x n bipartite graph. Any algorithm for this classical question clearly requires Ω(n2) time, and the best known one (Edmonds and Karp, 1972) finds solution in O(n3). For decades, it has remained unknown whether optimal computation time is closer to n3 or n2. We provide answer to this question for random instance of assignment problem. Specifically, we establish that Belief Propagation finds solution in O(n2) time when edge-weights are i.i.d. with light tailed distribution.