What is the difference between expected cost and average cost of an algorithm? While going through probabilistic/average analysis of an algorithm, I found written somewhere that average cost and expected cost are same. Can anyone please tell me what does exactly expected cost stands for.I think we take care of likelihood of an event while finding expected cost unlike average cost.
In short, the average is the expected value of the uniform distribution.

If $T(x)$ denotes the runtime of some algorithm on input $x \in \mathcal{X}$, then the expected runtime for input size $n$ is

$\qquad\displaystyle \mathbb{E}[T(X) \mid |X| = n] = \sum_{x\in\mathcal{X}_n} \operatorname{Pr}[X=x \mid |X| = n] \cdot T(x)$

given some random distribution for random variable $X$.

Average runtime is more specific and corresponds to

$\qquad\displaystyle \overline{T}(n) = \frac{1}{|\mathcal{X}_n|} \cdot \sum_{x\in\mathcal{X}_n} T(x)$

or, in other words, the expected runtime given a uniform distribution over inputs of the same size.

Since we usually use the uniform distribution the terms are often used interchangeably in algorithm analysis.