My algorithm is implemented in two steps;
- The computational complexity of the first step is $\mathcal{O}(NK)$;
- The computational complexity of the second step is $\mathcal{O}(MK)$;
I have already known that
- $M\leq N$
- M is a random variable, and the mean value of $M$ is difficult to be derived;
Can I say: the computational complexity of my algorithm is $\mathcal{O}((N+M)K)$?
Must I eliminate the uncertainty of $M$ (I am writing a journal paper)?
Yes, the computational complexity of your algorithm is $\mathcal{O}((N+M)K)$. You needn't eliminate the uncertainty of $M$.
Basically, you can put whatever parameters into the big $O$-notation, including input parameters, output parameters, machine configuration parameters, etc. as long as no harmful undefined-ness/ambiguities may arise when your readers/colleagues/referees interpret your big $O$-notation. If you can define $\mathcal{O}((N+M)K)$ in mathematical term naturally (which should involve probability) that fits your situation, you should be good to go with it.
A minor note might be in order. The exact meaning/intention of big $O$-notation on multiple variables is investigated rigorously and comprehensively only very recently, although it has been used widely and matter-of-factly far earlier. Check O-notation in algorithm analysis, October 2016 by Kalle Rutanen.
By the way, since $M<N$, we have $\mathcal{O}((N+M)K)=\mathcal{O}(NK)$, however your big $O$-notation of two-or-three variables are defined, assuming that $N$, $M$, and $k$ are nonnegative. So I would recommend you use $\mathcal{O}(NK)$.