Initial Disclaimer: I decided not to post this on Stack Overflow as my problem lies with understanding the mathematics of this problem, but does not relate to theory at all.
I am studying Parallel Programming and am trying to understand the computation complexity of bitonic sort. Specifically when a hypercube interconnection network is used and there is a block of elements per processor. None of this matters for the problem at hand, but might give insight to others who are familiar with the subject.
I am confused by the following algebraic function
where E is defined as
E = $\frac{S}{p}$
Where p is a variable. My problem is that I can not figure out how they obtained the simplified expression for E.
For my question regarding the theory of this problem, please refer to this
So this is going to be a pain to type out the steps but when it comes to big-O math things are pretty darn simple. The big-O hides almost everything. So for us that means $\mathcal{O}(ab) = \mathcal{O}(a)\mathcal{O}(b)$, $\mathcal{O}(a/b) = \mathcal{O}(a)/\mathcal{O}(b)$, $\mathcal{O}(a - b) = \mathcal{O}(a) - \mathcal{O}(b)$, $\mathcal{O}(a + b) = \mathcal{O}(a) + \mathcal{O}(b)$, and $\mathcal{O}(n^k) = \mathcal{O}(n)^k$.
Factoring out the denominator and splitting the numerator we can safely start here:
$$ S = \frac{\mathcal{O}(n) \mathcal{O}(\log{n})}{\mathcal{O}(\frac{n}{p})[\mathcal{O}(\log{\frac{n}{p}}) + \mathcal{O}(\log^2{p})]} $$
Flipping the $n/p$ we can move to:
$$ S = \frac{\mathcal{O}(p) \mathcal{O}(\log{n})}{[\mathcal{O}(\log{\frac{n}{p}}) + \mathcal{O}(\log^2{p})]} $$
Then $\log{n/p} = \log{n} - \log{p}$ so:
$$ S = \frac{\mathcal{O}(p) \mathcal{O}(\log{n})}{\mathcal{O}(\log{n}) - \mathcal{O}(\log{p}) + \mathcal{O}(\log^2{p})} $$
Now divide by $p$ (which is $\mathcal{O}(p)$ in big-O notation) to switch over to $E$:
$$ E = \frac{S}{p} = \frac{\mathcal{O}(\log{n})}{\mathcal{O}(\log{n}) - \mathcal{O}(\log{p}) + \mathcal{O}(\log^2{p})} $$
Finally multiply by $1 = \frac{ \frac{1}{\mathcal{O}(\log{n})} }{ \frac{1}{\mathcal{O}(\log{n})} }$ to arrive at:
$$ E = \frac{S}{p} = \frac{1}{1 - \frac{\mathcal{O}(\log{p})}{\mathcal{O}(\log{n})} + \frac{\mathcal{O}(\log^2{p})}{\mathcal{O}(\log{n})}} $$
Combine the big-Os to see the exact output you desired. Voila.