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 Ω(*n*^{2}) time, and the best known one (Edmonds and Karp, 1972) finds solution in *O*(*n*^{3}). For decades, it has remained unknown whether optimal computation time is closer to *n*^{3} or *n*^{2}. We provide answer to this question for random instance of assignment problem. Specifically, we establish that Belief Propagation finds solution in *O*(*n*^{2}) time when edge-weights are i.i.d. with *light tailed* distribution.