Why is $O(\log_{M/B} N/M)$ the same as $O(\log_{M/B} N/B)$? Where $N$ is the size of the input, $M$ is the size of your main memory and $B$ the amount of elements that you can transfer in one I/O.

My idea is that since $B$ is usually much smaller than $M$ we can have

$O\left(\frac{N}{B}\log_{\frac{M}{B}}\frac{N}{M}\right) = O\left(\frac{N}{B}\log_{\frac{M}{B}}\frac{NB}{MB}\right)$

so $\frac{B}{M} &lt;1$

but I'm new to complexity theory so I'm not sure if it's the correct reasoning.
Your construction will work just fine:
$$\begin{align}
\log_{M/B}\frac{N}{M}&amp;=\log_{M/B}\frac{NB}{BM}=\log_{M/B}\frac{N}{B}\cdot\frac{B}{M}\\
 &amp;= \log_{M/B}\frac{N}{B}+\log_{M/B}\frac{B}{M}\\
 &amp;= \log_{M/B}\frac{N}{B}-1
\end{align}$$
Since the two terms differ by 1, they're asymptotically equal.