  This paper focuses on the time constant for last passage percolation on
complete graph. Let $G_n=([n],E_n)$ be the complete graph on vertex set
$[n]=\{1,2,\ldots,n\}$, and i.i.d. sequence $\{X_e:e\in E_n\}$ be the passage
times of edges. Denote by $W_n$ the largest passage time among all
self-avoiding paths from 1 to $n$. First, it is proved that $W_n/n$ converges
to constant $\mu$, where $\mu$ is called the time constant and coincides with
the essential supremum of $X_e$. Second, when $\mu<\infty$, it is proved that
the deviation probability $P(W_n/n\leq \mu-x)$ decays as fast as
$e^{-\Theta(n^2)}$, and as a corollary, an upper bound for the variance of
$W_n$ is obtained. Finally, when $\mu=\infty$, lower and upper bounds for
$W_n/n$ are given.

Probability