# Hypercube - (n-1) coordinate plus one more dimension - Could be used in [[parallelism|parallel processing]], with vertices as processors, and edges connecting them - Construction - Make a copy of the `d`-dim hypercube, from `c` to `c'` - Connect the corresponding vertices in `c` and `c'` by edges. - Deriving the number of edges: $ \begin{cases} \displaystyle E(n) = 2E\left(\frac n2\right) + \frac n2 \\ E(2) = 1 \end{cases} \Rightarrow E(n) = O(n\log n) $ - Distance between nodes is $O(\log n)$, by jumping to the same sub-cube on and on. - Meanwhile, the mesh structure - Has a fixed degree (4) - Distance between nodes can be $\sqrt n$ - Cutting the mesh horizontally and vertically into 4 sub-meshes $ \begin{cases} \displaystyle E_m(n) = 4E_m\left(\frac n4\right) + 2\sqrt n \\ E(1) = 0 \end{cases} $ - Complete [[binary-tree]] (cutting from the root into 2 sub-trees) $ \begin{cases} \displaystyle E_T(n) = 2E_T\left(\frac{n-1}2\right) + 2 \\ E_T(1) = 0 \end{cases} $