In the article An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits I found statement (pg. 4):
Preparing an initial state takes $\log_2(N)$ steps.
In this case the initial state is uniformly distributed superposition of $n$ qubits where some states from computational basis are missing (example for two qubits: $\frac{1}{\sqrt{3}}(|00\rangle + |01\rangle+|11\rangle)$). Since $N=2^n$ the statement above means that complexity of preparing such state is linear in number of qubits.
In case all computational basis states are present in the required state, it is possible to use $H^{\otimes n}$ gate for preparing such state and in this case number of steps is even constant under assumpation that all Hadamard gates can be applied at once on all qubits.
However, since some computational basis states are missing, more complex circuit involving CNOT gates has to be constructed. In article Transformation of quantum states using uniformly controlled rotations, a general method how to produce arbitrary quantum state is proposed. Of course, this method is also suitable for preparing equally distributed states. However, the method leads to exponential incerease in gates number with increasing number of qubits.
So, my question is: What is a complexity of preparing uniformlly distributed states with some missing computational basis states? Is it really linear in number of qubits?